P4881 hby与tkw的基情

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;
}