相关链接
题目传送门: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; }