luogu P4881 hby与tkw的基情

背景博客还有好多没写看看这个周日有空吗。题目传送门https://www.luogu.org/problem/P4881题意求a n s ∑ i 1 n i ⋅ f i [ n m o d ThinSpace;ThinSpace; 2 ] ans\sum_{i1}^{n}i\cdot f_i[n\mod 2]ans∑i1n​i⋅fi​[nmod2]其中f i f_ifi​表示字符集为小写字母的回文串的个数。思路考虑回文串的前一段显然f i 2 6 ⌈ i 2 ⌉ f_i26^{\lceil\frac{i}{2}\rceil}fi​26⌈2i​⌉。那么有a n s ∑ i 1 n i ⋅ 2 6 ⌈ i 2 ⌉ [ i m o d ThinSpace;ThinSpace; 2 1 ] ans\sum_{i1}^{n}i\cdot26^{\lceil\frac{i}{2}\rceil}[i\mod 21]ansi1∑n​i⋅26⌈2i​⌉[imod21]考虑用k kk枚举奇数有a n s ∑ k 1 ⌈ n 2 ⌉ ( 2 k − 1 ) ⋅ 2 6 ⌈ 2 k − 1 2 ⌉ ans\sum_{k1}^{\lceil\frac{n}{2}\rceil}(2k-1)\cdot26^{\lceil\frac{2k-1}{2}\rceil}ansk1∑⌈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}amp;(1)\ ans\sum_{k1}^{\lceil\frac{n}{2}\rceil}(2k-1)\cdot26^{k}\\ amp;(2)\ 26ans\sum_{k1}^{\lceil\frac{n}{2}\rceil}(2k-1)\cdot26^{k1}\end{aligned}​(1)ansk1∑⌈2n​⌉​(2k−1)⋅26k(2)26ansk1∑⌈2n​⌉​(2k−1)⋅26k1​( 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-2626^{\lceil\frac{n}{2}\rceil1}n\sum_{i2}^{\lceil\frac{n}{2}\rceil}-2\cdot26^i25ans−2626⌈2n​⌉1ni2∑⌈2n​⌉​−2⋅26ia n s − 26 2 6 ⌈ n 2 ⌉ 1 n − 2 ∑ i 2 ⌈ n 2 ⌉ 2 6 i 25 ans\frac{-2626^{\lceil\frac{n}{2}\rceil1}n-2\sum_{i2}^{\lceil\frac{n}{2}\rceil}26^i}{25}ans25−2626⌈2n​⌉1n−2∑i2⌈2n​⌉​26i​后面就是一个等比数列求和化简一下就可以了这个在草稿本上写写即可。n m o d ThinSpace;ThinSpace; 2 0 n\mod20nmod20时让n − 1 n-1n−1即可反正第n nn项不产生贡献其实是我不特判会wrong answer \text{wrong answer}wrong answer。代码#includecstdio#includecstring#includealgorithm#defineLL long long#definemod 1000000007#defineinv25 280000002usingnamespacestd;LL n;LLksm(LL x,LL k){LL tot1;for(;k;k1){if(k1)tottot*x%mod;xx*x%mod;}returntot;}LLcalc(LL x){return(-26ll*26llksm(26,x1)mod)%mod*inv25%mod;}intmain(){intT;scanf(%d,T);while(T--){scanf(%lld,n);if(!(n1))n--;printf(%lld\n,(-26llksm(26,(n1)/21)*n%mod-2ll*calc((n1)/2)%modmod)%mod*inv25%mod);}}