luogu P4881 hby与tkw的基情

背景：

博客还有好多没写，看看这个周日有空吗。

题目传送门：

https://www.luogu.org/problem/P4881

题意：

求：a n s = ∑ i = 1 n i ⋅ f i [ n m o d    2 ] ans=\sum_{i=1}^{n}i\cdot f_i[n\mod 2]ans=∑i=1n​i⋅fi​[nmod2]，其中f i f_ifi​表示字符集为小写字母的回文串的个数。

思路：

考虑回文串的前一段，显然f i = 2 6 ⌈ i 2 ⌉ f_i=26^{\lceil\frac{i}{2}\rceil}fi​=26⌈2i​⌉。
那么有：
a n s = ∑ i = 1 n i ⋅ 2 6 ⌈ i 2 ⌉ [ i m o d    2 = 1 ] ans=\sum_{i=1}^{n}i\cdot26^{\lceil\frac{i}{2}\rceil}[i\mod 2=1]ans=i=1∑n​i⋅26⌈2i​⌉[imod2=1]

考虑用k kk枚举奇数，有：
a n s = ∑ k = 1 ⌈ n 2 ⌉ ( 2 k − 1 ) ⋅ 2 6 ⌈ 2 k − 1 2 ⌉ ans=\sum_{k=1}^{\lceil\frac{n}{2}\rceil}(2k-1)\cdot26^{\lceil\frac{2k-1}{2}\rceil}ans=k=1∑⌈2n​⌉​(2k−1)⋅26⌈22k−1​⌉

( 1 ) a n s = ∑ k = 1 ⌈ n 2 ⌉ ( 2 k − 1 ) ⋅ 2 6 k ( 2 ) 26 a n s = ∑ k = 1 ⌈ n 2 ⌉ ( 2 k − 1 ) ⋅ 2 6 k + 1 \begin{aligned}&(1)\ ans=\sum_{k=1}^{\lceil\frac{n}{2}\rceil}(2k-1)\cdot26^{k}\\ &(2)\ 26ans=\sum_{k=1}^{\lceil\frac{n}{2}\rceil}(2k-1)\cdot26^{k+1}\end{aligned}​(1)ans=k=1∑⌈2n​⌉​(2k−1)⋅26k(2)26ans=k=1∑⌈2n​⌉​(2k−1)⋅26k+1​

( 2 ) − ( 1 ) (2)-(1)(2)−(1)（考虑2 6 o p 26^{op}26op次方一起计算，o p ∈ [ 1 , ⌈ n 2 ⌉ ] ∩ N + op∈[1,\lceil\frac{n}{2}\rceil]∩N_+op∈[1,⌈2n​⌉]∩N+​）得：
25 a n s = − 26 + 2 6 ⌈ n 2 ⌉ + 1 n + ∑ i = 2 ⌈ n 2 ⌉ − 2 ⋅ 2 6 i 25ans=-26+26^{\lceil\frac{n}{2}\rceil+1}n+\sum_{i=2}^{\lceil\frac{n}{2}\rceil}-2\cdot26^i25ans=−26+26⌈2n​⌉+1n+i=2∑⌈2n​⌉​−2⋅26i

a n s = − 26 + 2 6 ⌈ n 2 ⌉ + 1 n − 2 ∑ i = 2 ⌈ n 2 ⌉ 2 6 i 25 ans=\frac{-26+26^{\lceil\frac{n}{2}\rceil+1}n-2\sum_{i=2}^{\lceil\frac{n}{2}\rceil}26^i}{25}ans=25−26+26⌈2n​⌉+1n−2∑i=2⌈2n​⌉​26i​

后面就是一个等比数列求和，化简一下就可以了，这个在草稿本上写写即可。
n m o d    2 = 0 n\mod2=0nmod2=0时，让n − 1 n-1n−1即可，反正第n nn项不产生贡献，其实是我不特判会wrong answer \text{wrong answer}wrong answer。

代码：

#include<cstdio>#include<cstring>#include<algorithm>#defineLL long long#definemod 1000000007#defineinv25 280000002usingnamespacestd;LL n;LLksm(LL x,LL k){LL tot=1;for(;k;k>>=1){if(k&1)tot=tot*x%mod;x=x*x%mod;}returntot;}LLcalc(LL x){return(-26ll*26ll+ksm(26,x+1)+mod)%mod*inv25%mod;}intmain(){intT;scanf("%d",&T);while(T--){scanf("%lld",&n);if(!(n&1))n--;printf("%lld\n",(-26ll+ksm(26,(n+1)/2+1)*n%mod-2ll*calc((n+1)/2)%mod+mod)%mod*inv25%mod);}}