目指すのはあの太阳 おおきな辉きを捕まえる
明明这次又要出去旅游了,和上次不同的是,他这次要去宇宙探险!
我们暂且不讨论他有多么NC,他又幻想了他应该带一些什么东西.理所当然的,你当然要帮他计算携带N件物品的方案数.
注意,这里我们懒得考虑明明对于带的食物该怎么搭配着吃,也认为每种食物都是以'个'为单位(反正是幻想嘛),只要总数加起来是N就算一种方案.因此,对于给出的N你需要计算出方案数,并对10007取模.
对于40%的数据,1<=N<=100000;
对于所有数据,1<=n<=10^500;
汉堡:1+x^2+x^4+......=1/(1-x^2)
蜜桃多:x+x^3+x^5+......=x/(1-x^2)
鸡块:1+x^4+x^8+......=1/(1-x^4)
包子:1+x+x^2+x^3
土豆:1+x
面包:1+x^3+x^6+......=1/(1-x^3)
↑先搞出这些东西的生成函数,全都乘起来得到x*(1-x)^(-4)
然后用广义二项式定理进行奇奇怪怪的转换,发现(1-x)^4的第n项系数为C(n+33)因为外面还有一个x,所以答案所在位置要左移一位,系数为C(n+23)
本文为博主原创文章,转载请注明出处.