题目概述

HDU7057

解题报告

首先这道题很显然可以用生成函数做，但是 $n$​ 太大了，因此需要考虑类似矩阵快速幂或者分治的办法。

定义 $F_i$​​ 表示花费 $i$​​ 时的生成函数，那么不难得出递推：$F_i=(1+x+x^2)F_{i-1}+(x+2x^2+x^3)F_{i-2}$ 。分别表示单独取和捆绑取的方案。

这很明显可以利用矩阵快速幂优化转移，但是常数巨大。我们还可以考虑分治。

对于 $n$​​ ，我们可以先求出 $L=\lfloor{n\over 2}\rfloor,R=n-L$​ 的 $F_L,F_R$​ 以及 $F_{L-1},F_{R-1}$ ，然后：

$$ F_n=F_LF_R+(x+2x^2+x^3)F_{L-1}F_{R-1} $$

也就是考虑中间那两个点是否需要捆绑，这样分治可以不遗漏的统计到所有位置是否捆绑的方案。

记忆化一下复杂度就正常了，为 $O(m\log_2m\log_2n)$​ 。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;typedef vector<int> PN;
const int maxt=1<<16,MOD=998244353;

int te,n,K;PN tem,ans;
unordered_map<int,PN> f;
int rev[maxt+5],pw[2][maxt+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=MUL(g,gn))
                x=a[i+j],y=MUL(a[i+j+k],g),a[i+j]=ADD(x,y),a[i+j+k]=ADD(x,MOD-y);
    }
    if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=MUL(a[i],INV);
}
PN operator * (const PN &a,const PN &b){
    static int A[maxt+5],B[maxt+5];static PN c;
    int n=a.size(),m=b.size(),t;
    for (t=1;t<=n+m-2;t<<=1);Pre(t);
    for (int i=0;i<n;i++) A[i]=a[i];for (int i=0;i<m;i++) B[i]=b[i];
    for (int i=n;i<t;i++) A[i]=0;for (int i=m;i<t;i++) B[i]=0;
    NTT(A,t,1);NTT(B,t,1);
    for (int i=0;i<t;i++) A[i]=MUL(A[i],B[i]);
    NTT(A,t,-1);
    int lim=min(n+m-1,K+1);c.resize(lim);
    for (int i=0;i<lim;i++) c[i]=A[i];
    return c;
}
PN operator + (const PN &a,const PN &b){
    static PN c;int n=a.size(),m=b.size();
    if (n>m){
        c.resize(n);
        for (int i=0;i<m;i++) c[i]=ADD(a[i],b[i]);
        for (int i=m;i<n;i++) c[i]=a[i];
        return c;
    } else {
        c.resize(n);
        for (int i=0;i<n;i++) c[i]=ADD(a[i],b[i]);
        for (int i=n;i<m;i++) c[i]=b[i];
        return c;
    }
}
PN Solve(int n){
    if (f.count(n)) return f[n];
    int L=n/2,R=n-L;
    PN a=Solve(L)*Solve(R);
    PN b=tem*Solve(L-1)*Solve(R-1);
    return f[n]=a+b;
}
void Make(){
    f.clear();
    f[0].resize(1);f[0][0]=1;
    f[1].resize(3);f[1][0]=f[1][1]=f[1][2]=1;
}
int main(){
    tem.resize(4);tem[0]=0;tem[1]=1;tem[2]=2;tem[3]=1;
    for (scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&K);Make();ans=Solve(n);
        for (int i=1,si=ans.size();i<si && i<=K;i++) printf("%d ",ans[i]);
        for (int i=ans.size();i<=K;i++) putchar('0'),putchar(' ');puts("");
    }
    return 0;
}