题解：P6811 「MCOI-02」Build Battle 建筑大师

· · 题解

设 f_i 为匹配到第 i 为的序列个数，令 last_{x,i} 表示从第 i 为往前第一个出现 x 的位置，可以得到转移 f_i=\sum_{j=last_{a_i,i}}^{i-1}{f_j}。最后答案即为 \sum{f}。

由于本题 a 的特殊性，所有 last 都满足 last_{x,i}=i-m。带入上式得到 f_i=\sum_{j=i-m}^{i-1}{f_j}。使用前缀和优化，可以 O(n) 求出，总复杂度 O(n^2)。

继续考虑如何优化，我们对 f 求前缀和，记前缀和数组为 s，最终答案即为 s_n。根据 f 的递推式，显然有 s_i=s_{i-m-1}+2 \times f_i=s_{i-m-1} + 2 \times (s_{i-1} - s_{i-m-1}) = 2\times s_{i-1} - s_{i-m-1}。

想想如何快速求出 s_n，考虑其组合意义，我们可以想成从 i=0 处开始走，每步消耗一定代价，每次可以选择以下两种走法（记上一步代价为 lastv 且初始为 1，这一步为 v）：

  1. 让 i+1 \to i，花费代价 v=2\times lastv；

  2. 让 i+m+1 \to i，花费代价 v=-lastv；

最后答案 s_n 即为走到 i=n 时所有 v 的和。记第一种操作次数为 x，第二种为 y。我们就可以直接枚举 y，由于 x + y\times (m + 1) = n 得到 x=n-y\times(m+1)，那么消耗的代价就是

2^{x}\times(-1)^{y} \times {{x+y} \choose {x}}=2^{n-y\times(m+1)}\times(-1)^{y}\times{{n-y\times(m+1)+y}\choose{y}}

于是有

s_n=\sum_{y=0}^{\lfloor\frac{n}{m+1}\rfloor}{2^{n-y\times(m+1)}\times(-1)^{y}\times{{n-y\times(m+1)+y}\choose{y}}}

接下来只要枚举 m 即可，总复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define MAXN 2000005
#define int long long
using namespace std;
const int inf=1e18,mod=1e9+7;
int fpow(int a,int b){
    int tans=1;
    while(b){
        if(b&1)tans=tans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return tans;
}
int n,q,a[MAXN],ans[MAXN];
int fac[MAXN],ifac[MAXN],p[MAXN];
void init(){
    fac[0]=ifac[0]=p[0]=1;
    for(int i=1;i<=n*2;i++){
        fac[i]=fac[i-1]*i%mod;
        ifac[i]=ifac[i-1]*fpow(i,mod-2)%mod;
        p[i]=p[i-1]*2%mod;
    }
}
int C(int n,int m){
    if(n<m)return 0;
    return fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld%lld",&n,&q);
    init();
    for(int i=1;i<=n;i++){
        int m=i;
        for(int j=0;j<=n/(m+1);j++){
            if(j&1)ans[m]=(ans[m]+mod-p[n-j*(m+1)]*C(n-j*(m+1)+j,j)%mod)%mod;
            else ans[m]=(ans[m]+p[n-j*(m+1)]*C(n-j*(m+1)+j,j)%mod)%mod;
        }
    }
    for(int i=1;i<=q;i++){
        int x;scanf("%lld",&x);
        printf("%lld\n",ans[x]);
    }
    return 0;
}