c/c++语言开发共享BZOJ2655: calc(dp 拉格朗日插值)

题意

题目链接

sol

首先不难想到一个dp

设(f[i][j])表示选了(i)个严格递增的数最大的数为(j)的方案数

转移的时候判断一下最后一个位置是否是(j)

[f[i][j] = f[i][j – 1] + f[i – 1][j – 1] * j]

for(int i = 0; i <= a; i++) f[0][i] = 1; for(int i = 1; i <= n; i++)     for(int j = 1; j <= a; j++)          f[i][j] = add(f[i][j - 1], mul(f[i - 1][j - 1], j)); cout << mul(f[n][a], fac[n]);

发现还是不好搞，把转移拆开

(f[i][j] = sum_{k = 0}^{j – 1} f[i – 1][k] * (k + 1))

这个转移就非常有意思了

我们如果把(i)看成列，(k)看成行，那么转移的时候实际上就是先对第(k)行乘上一个系数(k)，然后再求和

如果我们把第(i – 1)列看成一个(t)次多项式，显然第(i)列是一个(t+2)次多项式(求和算一次，乘系数算一次)

这样的话第(i)列就是一个最高(2i+1)次多项式

插一插就好了

// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int maxn = 10001; int a, n, lim, mod, f[501][maxn], fac[maxn], y[maxn]; int add(int x, int y) {     if(x + y < 0) return x + y + mod;     return x + y >= mod ? x + y - mod : x + y; } void add2(int &x, int y) {     if(x + y < 0) x = (x + y + mod);     else x = (x + y >= mod ? x + y - mod : x + y); } int mul(int x, int y) {     return 1ll * x * y % mod; } int fp(int a, int p) {     int base = 1;     while(p) {         if(p & 1) base = mul(base, a);         a = mul(a, a); p >>= 1;     }     return base; } int large(int *y, int k) {     static int x[maxn], ans = 0;     for(int i = 1; i <= lim; i++) x[i] = i;     for(int i = 0; i <= lim; i++) {         int up = y[i], down = 1;         for(int j = 0; j <= lim; j++) {             if(i == j) continue;             up = mul(up, add(k, -x[j]));             down = mul(down, add(x[i], -x[j]));         }         add2(ans, mul(up, fp(down, mod - 2)));     }     return ans; } int main() { #ifndef online_judge     freopen("a.in", "r", stdin);    // freopen("a.out", "w", stdout); #endif     cin >> a >> n >> mod; lim = 2 * n + 1;     fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = mul(i, fac[i - 1]);     for(int i = 0; i <= lim; i++) f[0][i] = 1;     for(int i = 1; i <= n; i++) {         for(int j = 1; j <= lim; j++) {             f[i][j] = add(f[i][j - 1], mul(f[i - 1][j - 1], j));         }     }     for(int i = 0; i <= lim; i++) y[i] = f[n][i];     cout << mul(large(y, a), fac[n]);     return 0; }