题目
做法
我们先求出每一种食物的生成函数
承德汉堡:(1 + x^2 + x^4 + cdots = frac{1}{1-x^2})
可乐:(1 + x = frac{1-x^2}{1-x})
鸡腿:(1 + x + x^2 = frac{1-x^3}{1-x})
蜜桃多:(x + x^3 + x^5 + cdots = frac{x}{1-x^2})
鸡块:(1 + x^4 + x^8 + x^12 + cdots = frac{1}{1-x^4})
包子:(1 + x + x^2 + x^3 = frac{1-x^4}{1-x})
土豆片炒肉:(1 + x = frac{1-x^2}{1-x})
面包:(1 + x^3 + x^6 + x^9 + cdots = frac{1}{1-x^3})
设(F(x))为答案的生成函数, 则
[egin{aligned}
F(x) &=
frac{1}{1-x^2} imes frac{1-x^2}{1-x} imes frac{1-x^3}{1-x} imes frac{x}{1-x^2} imes frac{1}{1-x^4} imes frac{1-x^4}{1-x} imes frac{1-x^2}{1-x} imes frac{1}{1-x^3}\
&= frac{{(1-x^2)}^2(1-x^3)(1-x^4)x}{(1-x)^4{(1-x^2)}^2(1-x^4)(1-x^3)}\
&= frac{x}{(1-x)^4}
end{aligned}
]
于是我们要求([x^n]F(x))
我们发现其实求的就是(a + b + c + d = n-1)的方案数
这可以用插板法很方便的求出, 答案是({{n+2} choose 3})
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL mod = 10007;
char str[510];
int main()
{ LL n = 0;
scanf("%s", str);
int len = strlen(str);
for (int i = 0; i < len; i++)
n = (n * 10 + str[i] - '0') % mod;
printf("%lld
", n * (n + 1) % mod * (n + 2) % mod * 1668LL % mod);
return 0;
}