题意简述
$T$组数据。给定$n,m$,求$(x^2+x+1)^n$中,$x^m$项的系数是多少。答案对$3$取膜。
(这个膜数很神奇!注意!突破点就在这!)
$T<=1e4$,$n<=1e15$,$m<=2n$。
思路框架
答案是$C_{2n}^m\times (m\% 2+1)$,对$3$取膜(写个$Lucas$即可)
具体思路
首先,我们分括号讨论。因为是$(x^2+x+1)^n$,所以有$n$个括号,并且每个括号可以出$x^2,x,1$。然后我们要求,有多少种方案使得每个括号中出的数积为$x^m$。
我们开始打草稿:我们把$n$个括号从$1$到$n$顺序编号,每个括号上面有两个复选框。打了几个勾,就是代表出$x$的多少次方。具体来说就是:
一个都没打勾,代表出$x^0$($x^0$就是$1$);其中一个打了勾,代表出$x$;两个都打了勾,代表出$x^2$。
如图所示是$n=4$的情况:
我们这样勾选:
那就相当于:
第一个括号出$x$
第二个括号出$x^2$
第三个括号出$x$
第四个括号出$x$
那它就会给$x^5$那一项贡献一种情况。
那么我们现在考虑$x^m$项的系数,换句话说就是有多少种方法凑出$x^m$。
显然,上面的复选框中,我们每打一个勾,乘出来就多一个$x$。(上面打了$5$个勾,乘起来就是$x^5$)然后一共有$2n$个复选框,所以答案就是$C_{2n}^m$。
这就完了?不!这样考虑有重复的!
假如第$i$个括号出的是$x$,那就相当于在$i$上面两个复选框中,其中一个要打勾。而我们只在意数量,具体打勾打上面那个框还是下面的那个,是一样的。那就会把一个答案算两遍,所以要除以$2$。
假设我们有$k$个括号出的是$x$,那么我们的答案就要除以一个$2^k$。
首先,$k$和$m$肯定是同奇偶的。
稍微证一下(会证跳过): 有$k$个括号出$x$,那剩下$x^{m-k}$都是由出$1$或$x^2$组成的。$m-k$由若干个$0$和$2$相加而成,所以$m-k$是偶数。所以$m$和$k$同奇偶。
然后,在模三意义下,2的逆元就是其本身!所以,除以一个$2^k$,就相当于乘以一个$2^k$。
还没完,我们继续化。我们发现,$2$的幂除以$3$的余数是:$2,1,2,1,2,1…$。具体点说,$2^k\% 3=(k\% 2)+1$。而$k$和$m$又同奇偶,所以,所有的$k\% 2+1$都等于$m\% 2+1$。
综上,我们的答案就是$C_{2n}^m\times (m\% 2+1)$。
代码
1 |
|