自动搬运

查看原文

来自洛谷，原作者为

	Wolfycz **

搬运于2025-08-24 22:04:52，当前版本为作者最后更新于2018-09-10 10:21:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先要得出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;
}