相关链接
题目传送门: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; }
Hi, I think your site might be having browser compatibility issues. When I look at your blog in Chrome, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, awesome blog!
304561 464130Thanks for the write up! Also, just a heads up, your RSS feeds arent working. Could you take a appear at that? 173381
429290 752546Sorry for the huge review, but Im genuinely loving the new Zune, and hope this, as nicely as the superb reviews some other folks have written, will support you decide if its the best choice for you. 774456
770023 171836Heya just wanted to give you a brief heads up and let you know a few with the pictures arent loading properly. Im not sure why but I think its a linking issue. Ive tried it in two different internet browsers and both show exactly the same outcomes. 95714
I genuinely value your work, Great post.
585662 783405I conceive this web site contains some rattling superb information for everyone : D. 874240
400928 860001Exceptional blog here! Also your web site loads up extremely quick! What host are you utilizing? Can I get your affiliate link to your host? I wish my web site loaded up as quick as yours lol xrumer 64953
636658 940994There is noticeably a bundle to realize about this. I assume you produced specific good points in functions also. 317381
323445 67587Thank you for your data and respond to you. bad credit auto loans hawaii 850882
723528 131085Respect to post author, some amazing info . 834958
842941 298424Hello! Great stuff, please maintain us posted when you post once again something like that! 900852
510137 950680Great post man, keep the nice function, just shared this with the friendz 762725
864577 456353As I web site possessor I believe the content matter here is rattling magnificent , appreciate it for your hard work. You ought to keep it up forever! Finest of luck. 370430