相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3612
神犇题解:http://blog.csdn.net/Vmurder/article/details/42551603
解题报告
读题后我们发现需要求解这么一个问题:
用$k$个不同的数,来凑成$n$的方案数
这个看起来只能$O(kn^2)$来做$DP$
但我们可以将其优化到$O(nk)$
具体来说,考虑所有$k$个数,一起加或一起减
这样的话,我们就可以不用枚举新加入答案集合的数是哪一个了
回到原题,我们枚举左右两边取出来的重量,和左边用了几块橡皮
然后总的复杂度主要还是在$DP$那一块,复杂度是:$O(k^2n)$的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 11; int n,K,MOD,f[N][M]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } int main() { for (int T=read(),ans;ans=0,T;T--) { n = read(); K = read(); MOD = read(); memset(f,0,sizeof(f)); f[0][0] = 1; for (int i=1,lim=n*K;i<=lim;i++) { for (int k=1,LIM=min(i,K);k<=LIM;k++) { f[i][k] = (f[i-k][k] + f[i-k][k-1]) % MOD; if (i > n) f[i][k] = (f[i][k] - f[i-(n+1)][k-1]) % MOD; } } for (int i=0,lim=n*K;i<=lim;i++) { for (int k=0;k<K;k++) { ans = (ans + (LL)f[i][k] * f[i][K-k]) % MOD; ans = (ans + (LL)f[i][k] * f[i][K-k-1]) % MOD; } } printf("%d\n",(ans+MOD)%MOD); } return 0; }