luogu P6811 「MCOI-02」Build Battle 建筑大师

https://www.luogu.com.cn/problem/P6811

考虑建立子序列自动机，可以得到DP

f [ i ] = 1 + ∑ i + 1 ≤ j ≤ i + m f [ j ] f[i]=1+sum_{i +1 le j le i+m} f[j] f[i]=1+i+1≤j≤i+m∑​f[j]

答案就是 f [ 0 ] f[0] f[0]

考虑把整个DP数组反过来

f [ i ] = 1 + ∑ i − m ≤ j ≤ i − 1 f [ j ] f[i]=1+sum_{i - m le j le i-1} f[j] f[i]=1+i−m≤j≤i−1∑​f[j]
有个常数项感觉不太舒服，我们考虑用做差的方式去掉它

f [ i ] − f [ i − 1 ] + f [ i − 1 ] = f [ i − 1 ] − f [ i − m − 1 ] + f [ i − 1 ] = 2 f [ i − 1 ] − f [ i − m − 1 ] f[i]-f[i-1]+f[i-1]=f[i-1]-f[i-m-1]+f[i-1] \ =2f[i-1]-f[i-m-1] f[i]−f[i−1]+f[i−1]=f[i−1]−f[i−m−1]+f[i−1]=2f[i−1]−f[i−m−1]

这个式子我们可以构造它的组合意义

一个人，向前走一步就 ∗ 2 *2 ∗2，向前走 m + 1 m+1 m+1步就 ∗ ( − 1 ) *(-1) ∗(−1)
于是我们可以枚举 m m m,然后再枚举走了几个 m + 1 m+1 m+1,通过组合数计算出方案数

这个显然是调和级数

代码实现不难

code:

#include
#define ll long long
#define N 2000050
#define mod 1000000007
using namespace std;
ll qpow(ll x, ll y) {
    ll ret = 1;
    for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
    return ret;
}
ll fac[N], ifac[N], pw[N], ans[N];
void init(int n) {
    fac[0] = pw[0] = 1;
    for(int i = 1; i <= n; i ++) fac[i] = fac[i - 1] * i % mod, pw[i] = pw[i - 1] * 2 % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; i >= 0; i --) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
ll C(int n, int m) {
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int n, m, q;
int main() {
    scanf("%d%d", &n, &q);
    init(n);
    for(int m = 1; m <= n; m ++) {
        for(int i = 0; i * (m + 1) <= n; i ++) {
            ll o = C(n - i * (m + 1) + i, i) * pw[n - i * (m + 1)] % mod;
            if(i & 1) ans[m] = (ans[m] - o + mod) % mod;
            else ans[m] = (ans[m] + o) % mod;
        }
    }
    while(q --) {
        scanf("%d", &m);
        printf("%lldn", ans[m]);
    }
    return 0;
}