题解：AT_aising2020_f Two Snuke

· · 题解

啄题。

感觉上 limit 都用指数来限制。

对于一个 (x,x+\Delta)，贡献是 \Delta，代价是 2x+\Delta。枚举：

\sum_{x \geq 0}\sum_{\Delta > 0}\Delta t^{2x+\Delta}=\sum_{x \geq 0}t^{2x}\sum_{\Delta > 0}\Delta t^{\Delta}\\ =\frac{t}{(1-t^2)(1-t)^2}

事实上，要选 5 对。然后有一个前缀和：

[t^{N}]\frac{t^5}{(1-t^2)^5(1-t)^{11}}

直接上 bostan-mori 就好了，O(k^2\log{N})，k 大概二十左右。

//begin 20:44
#include<bits/stdc++.h>
const int mod=1e9+7;
int fpow(int a,int b=mod-2){
    int r=1;
    while(b){
        if(b&1)r=1ll*r*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return r;
}
using namespace std;
#define poly vector<int>
poly mul(poly a,poly b){
    int n=(int)a.size()+(int)b.size()-1;
    poly r;r.clear();r.resize(n);
    for(int i=0;i<(int)a.size();i++){
        for(int j=0;j<(int)b.size();j++){
            r[i+j]=(r[i+j]+1ll*a[i]*b[j]%mod)%mod;
        }
    }
    return r;
}
int mori(poly f,poly g,int n){
    for(;n;n>>=1){
        poly gn=g;
        for(int i=1;i<(int)gn.size();i+=2)gn[i]=(mod-gn[i])%mod;
        f=mul(f,gn);g=mul(g,gn);
        int i;
        for(i=n&1;i<(int)f.size();i+=2)f[i>>1]=f[i];
        f.resize(i>>1);
        for(i=0;i<(int)g.size();i+=2)g[i>>1]=g[i];
        g.resize(i>>1);
    }
    if(f.empty())return 0;
    return 1ll*f[0]*fpow(g[0])%mod;
}
int T,n;
poly up,dn,tmp1,tmp2;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    up=poly(1,1);dn=poly(1,1);
    tmp1.resize(3),tmp2.resize(2);
    tmp1[0]=1,tmp1[2]=mod-1;tmp2[0]=1,tmp2[1]=mod-1;
    for(int i=1;i<=5;i++)dn=mul(dn,tmp1);
    for(int i=1;i<=11;i++)dn=mul(dn,tmp2);
    cin>>T;
    while(T--){
        cin>>n;
        if(n<5){cout<<"0\n";continue;}
        n-=5;
        cout<<mori(up,dn,n)<<'\n';
    }
}
//20:50

下播。