专栏文章

题解：AT_aising2020_f Two Snuke

aanalysis
AT_aising2020_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq7admw
此快照首次捕获于
2025/12/04 00:07
3 个月前
此快照最后确认于
2025/12/04 00:07
3 个月前
查看原文
啄题。
感觉上 limit 都用指数来限制。
对于一个 (x,x+Δ)(x,x+\Delta)，贡献是 Δ\Delta，代价是 2x+Δ2x+\Delta。枚举：
∑x≥0∑Δ>0Δt2x+Δ=∑x≥0t2x∑Δ>0ΔtΔ=t(1−t2)(1−t)2\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}
事实上，要选 55 对。然后有一个前缀和：
[tN]t5(1−t2)5(1−t)11[t^{N}]\frac{t^5}{(1-t^2)^5(1-t)^{11}}
直接上 bostan-mori 就好了，O(k2log⁡N)O(k^2\log{N})，kk 大概二十左右。
CPP
//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
下播。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...