hdu 4704 Sum (隔板法,指数循环节,费马小定理)

题目链接

题意:定义s(k)为将n分成k个正整数的划分数,给出n,问s(1) + s(2) + … + s(n-1) + s(n)是多少,结果%1E9+7,其中n<=10^100000。

思路:首先化简要求的式子。

根据隔板法_维基百科

现在有10个球,要放进3个盒子里

●●●●●●●●●●

隔2个板子,把10个球被隔开成3个部分

●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、……

如此类推,10个球放进3个盒子的方法总数为{{\binom {10-1}{3-1}}={\binom {9}{2}}=36

n个球放进k个盒子的方法总数为{{\binom {n-1}{k-1}}

问题等价于求{x_{1}+x_{2}+...+x_{k}=n的可行解数,其中x_{1},x_{2},...,x_{k}正整数

 

于是问题转化成:

n个木棍,n-1个缝,

分成1份则是C(n-1,0);

分成2份则是C(n-1,1);

分成3份则是C(n-1,2);

分成n份则是C(n-1,n-1);

ans = sum( C(n-1,i) ) (0<=i<=n-1)

=2^(n-1);

 

这是我能理解的得到2^(n-1)的方式。。。

看到有好多人说这个结论是显然的。。。求指教(说这是个结论记住就好的就算了23333)

接下来,就是求A=2^(n-1)%1E9+7的问题了。。。

根据指数循环节公式A=2^((n-1)%(mod-1))*2^(mod-1)%mod (其中mod=1E9+7)

由于gcd(2,1E9+7)=1,根据费马小定理2^(mod-1)%mod=1,因此A=2^((n-1)%(mod-1))

然后快速幂搞之。

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz