相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3028
神犇题解:http://blog.csdn.net/regina8023/article/details/44995939
解题报告
这题看上去一眼不可做啊!第一反应:还要写高精?
但想一想似乎物品非常妙妙:
我们强行将其分为四组:{汉堡,可乐} {蜜桃多,土豆片炒肉} {包子,鸡块} {鸡腿,面包}
我们发现每一组都能凑出每一个自然数,且方案唯一
于是问题变为将$n$个球分为$4$组,每组可以为空的方案数
这是插板法的经典问题,于是搞一个组合数就可以了
什么组合数太大?
我们注意到答案实际是$\frac{n^{\bar 3}}{6}$,所以我们取个模就可以了
当然你也可以强行搞生成函数然后泰勒展开得到一样的结论
但我不会泰勒展开 QwQ
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 10007; const int REV = 1668; int main() { int n=0; char pat[600]; cin>>pat+1; for (int i=1;i<=strlen(pat+1);i++) n = (n * 10 + pat[i] - '0') % MOD; cout<<n*(n+1ll)*(n+2)*REV%MOD; return 0; }
I enjoy the efforts you have put in this, thanks for all the great blog posts.
Hi would you mind letting me know which webhost you’re working with? I’ve loaded your blog in 3 completely different internet browsers and I must say this blog loads a lot quicker then most. Can you recommend a good web hosting provider at a honest price? Many thanks, I appreciate it!