P4881 hby与tkw的基情
Captain_Paul
2018-09-10 08:07:24
看到这题第一反应就是找规律(毕竟被小凯练出来了)
首先从$s[i]$入手,它表示长度为$i$的只包含小写字母的回文串个数
手算或者打表可以发现它是一个这样的数列
$26,26,26^2,26^2,26^3,26^3...$
这样就搞定了$s[i]$
再观察一下题目的式子,发现后面有个$i\%2$
那偶数项不就没有了?2333
这样就只需要求奇数项的和了
打个表看一下,只看奇数项的序列是这样的:
$1*26,3*26^2,5*26^3......(2n-1)*26^n$
那么每次询问要做的就是求出它的前$n$项之和
因为$n$非常大,所以不能直接求,先化简一下看一看
($26$看起来非常麻烦,把它写成$x$)
记$S=x+3x^2+5x^3+......+(2n-1)x^n$
则$xS=x^2+3x^3+5x^4+......+(2n-1)x^{n+1}$
用错位相减法,得$(1-x)S=x+2(x^2+x^3+x^4+......+x^n)-(2n-1)x^{n+1}$
中间括号内用等比数列求和公式,得
$(1-x)S=x+2x^2(1-x^{n-1})/(1-x)-(2n-1)x^{n+1}$
为了方便,两边同时取相反数,移项得
$S=[(2n-1)x^{n+1}-x-2x^2(x^{n-1}-1)/(x-1)]/(x-1)$
因为有模数,所以除法要用$25$在模$1e9+7$意义下的逆元
```
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=1e9+7,inv25=280000002;
int T,n;
ll quickpow(ll n,ll k)
{
ll s=1;
while (k)
{
if (k&1) s=s*n%mod;
n=n*n%mod; k>>=1;
}
return s;
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
if (!(n&1)) --n; n=(n+1)>>1;
ll x1=(2*n-1)*quickpow(26,n+1)%mod,x2=mod-26;
ll x3=1352*(quickpow(26,n-1)-1+mod)%mod*inv25%mod;
ll ans=(x1+x2-x3+mod)%mod*inv25%mod;
printf("%lld\n",ans);
}
return 0;
}
```