题解 P4881 【hby与tkw的基情】

· · 题解

首先要得出s[i]的递推式，s[i]=s[i-2]*26,s[1]=s[2]=26，然后T=1可以用矩乘快速幂，（O2可能可以AC所有数据）

我们发现这个式子实际上要求

Ans=\sum\limits_{i=1}^m(2i-1)\times 26^i

这个显然是差比数列，可以裂项相减

26Ans=\sum\limits_{i=1}^m(2i-1)\times 26^{i+1}

减去之前的式子有

25Ans=-26+(2n-1)\times 26^{n+1}-2\sum\limits_{i=2}^m 26^i

把-26挪到最后好看一些，然后把后面用等比数列求和来表示

25Ans=26+(2n-1)\times 26^{n+1}-2\times\dfrac{26^{n+1}-26}{25}

然后就可以直接算了

ps:我的代码做了一点优化，例如提取26^{n+1}这些同类项，减少了%和快速幂，但是按原式直接写也可以，大家可以自己推一下

/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}
inline void print(int x){
    if (x>=10)  print(x/10);
    putchar(x%10+'0');
}
const int p=1e9+7,inv=2.8e8+2,inv2=5.6e8+5;
int mlt(int a,int b){
    int res=1;
    for (;b;b>>=1,a=1ll*a*a%p)  if (b&1)    res=1ll*res*a%p;
    return res;
}
int main(){
    for (int T=read();T;T--){
        int n=(read()+1)>>1;
        int Ans=1ll*(1ll*mlt(26,n+1)*((n<<1)-inv2+p)%p+26ll*inv2%p)%p*inv%p;
        printf("%d\n",Ans);
    }
    return 0;
}