https://atcoder.jp/contests/arc104/tasks/arc104_d
ARC也太自闭了。。。完全不适合我这种只会模拟的而且模拟也写不好的低智选手，10分钟签完AB一看C也不会D也不会。。。
D需要一个牛逼的转化，我们最后的目标均值是x其实就是最后选出a集合中的元素要满足sum{ai-x}=0，所以其实每个数字就可以变成-1,-2,...-(x-1)，和+1,+2,...+N-x
我们发现由于每个数字可以选的数量都是一样的，所以把-1,-2...-(x-1)变成+1，+2，...+(x-1)，我们并不需要关心每个数字选了多少，只需要知道负数部分的和正数部分的和是一样的就行了，我们发现他们都是一个前缀，所以设dp[i][j]为1-i不超过K个能得到总和为j的方案数,j的值域就是K*N*(N-1)/2
那么我们要求x的方案，可知负数部分变成1...x-1，正数部分变成1...N-x，那么只要统计所有相同的总和对答案的贡献就行了
最后要*k+1，因为x这个数字本身是随便选多少个都不影响均值的，还要-1，因为统计了集合是空集的情况。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxl=110; int n,k,mod,lim;ll ans; ll dp[maxl][maxl*maxl*maxl]; inline void prework() { scanf("%d%d%d",&n,&k,&mod); lim=k*n*(n-1)/2; } inline void add(ll &x,ll y) { x=(x+y)%mod; if(x<0) x+=mod; } inline void mainwork() { dp[0][0]=1; for(int i=1;i<n;i++) { for(int j=0;j<=lim;j++) { dp[i][j]=dp[i-1][j]; if(j>=i) add(dp[i][j],dp[i][j-i]); } for(int j=lim;j>=(k+1)*i;j--) add(dp[i][j],-dp[i][j-(k+1)*i]); } } inline void print() { for(int x=1;x<=n;x++) { ans=0; for(int i=0;i<=lim;i++) add(ans,dp[x-1][i]*dp[n-x][i]); ans=ans*(k+1)%mod; ans=(ans-1+mod)%mod; printf("%lld\n",ans); } } int main() { int t=1; //scanf("%d",&t); for(int i=1;i<=t;i++) { prework(); mainwork(); print(); } return 0; }
