题解：P11284 「GFOI Round 2」Strings

· · 题解

本文除法全部下取整。

设 f_n 为长度 2n 最短偶回文前缀为 n 的序列个数。有转移：

f_n=m^n-\sum\limits_{i=1}^{n/2}f_im^{n-2i}

枚举答案序列最短偶回文前缀 2l，答案即为：

\sum\limits_{l=1}^{n/3}f_l\sum\limits_{i=3l}^nm^{i-2l} =\sum\limits_{l=1}^{n/3}f_lm^{-2l}\sum\limits_{i=3l}^nm^i =\sum\limits_{l=1}^{n/3}f_lm^{-2l}\dfrac{m^{3l}-m^{n+1}}{1-m}

容易发现答案可以被函数 S(n,k)=\sum\limits_{l=1}^nf_lm^{kl} 表示。

考虑递归计算，使用与对答案类似的处理技巧：

S(n,k)=\sum\limits_{l=1}^nf_lm^{kl} =\sum\limits_{l=1}^nm^{kl}(m^l-\sum\limits_{i=1}^{l/2}f_im^{l-2i}) =\sum\limits_{l=1}^nm^{(k+1)l}-\sum\limits_{l=1}^n\sum\limits_{i=1}^{l/2}f_im^{(k+1)l-2i}

前面部分可以等比数列求和，后半部分：

\sum\limits_{l=1}^n\sum\limits_{i=1}^{l/2}f_im^{(k+1)l-2i} =\sum\limits_{i=1}^{n/2}\sum\limits_{l=2i}^nf_im^{(k+1)l-2i} =\sum\limits_{i=1}^{n/2}m^{-2i}\sum\limits_{l=2i}^nf_im^{(k+1)l} =\sum\limits_{i=1}^{n/2}m^{-2i}\dfrac{m^{2i(k+1)}-m^{(n+1)(k+1)}}{1-m} =\dfrac{S(n/2,2k)-m^{(n+1)(k+1)}S(n/2,-2)}{1-m}

发现 S 只有 \dfrac{n}{2^a},\pm2^b 位置会被计算到，记忆化之。

时间复杂度 \mathcal{O}(T\log^2n(\log \textsf{mod}+\log n))。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<random>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define IV void
#define her1 20081214
#define cht 1000000007
#define ull unsigned long long
#define mem(x,val) memset(x,val,sizeof x)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
ll read(){
    ll ans=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
    return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
i64 qpow(i64 n,i64 base=cht-2){
    base%=(cht-1);n%=cht;
    if(base<0)base+=cht-1;
    i64 ans=1;
    while(base){
        if(base&1)ans=ans*n%cht;
        n=n*n%cht;base>>=1;
    }
    return ans;
}
IV cadd(i64&x,i64 val){x=(x+val)%cht;}
const int maxn = 1e5+5;
i64 n,m;
map<pair<i64,i64>,i64>mp;
i64 S(i64 n,i64 k){
    if(n==1)return qpow(m,k+1);
    if(mp.count({n,k}))return mp[{n,k}];
    i64 Ans=0,pw=qpow(m,k+1);
    if(pw==1)Ans=n;
    else Ans=qpow(pw-1)*(qpow(pw,n+1)-qpow(pw,1))%cht;
    i64 s=(S(n/2,2*k)-S(n/2,-2)*qpow(m,(n%(cht-1)+1)*(k%(cht-1)+1)))%cht;
    s=s*qpow(1-qpow(m,k+1))%cht;
    return mp[{n,k}]=(Ans-s)%cht;
}
IV solve(){
    n=read();m=read();mp.clear();
    if(m==1)return(void)(printf("%lld\n",(n-2)%cht));
    i64 Ans=(S(n/3,1)-S(n/3,-2)*qpow(m,n+1))%cht;
    printf("%lld\n",(Ans*qpow(1-m)%cht+cht)%cht);
}
int main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    i64 T=read();while(T--)solve();return 0;
}