P4881 hby与tkw的基情

看到这题第一反应就是找规律（毕竟被小凯练出来了） 首先从$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; } ```