BZOJ 2655 calc

拉格朗日插值优化dp。

显然可以得到\(dp\) :

\(f[i][j] = f[i - 1][j - 1] \times j + f[i][j-1]\)

表示前\(i\)个数用\([1,j]\)且单增的\(ans\), 题目要求的即为\(f[n][A]\times n!\)。

\(f(n,j)\)转移时 有\(f(n,j) - f(n, j-1)= f(n -1 , j - 1) \times j\)

引用结论 : \(g(x)\)是关于\(x\)的\(n\)次多项式的情况下 \(g(x) - g(x-1)\)为\(n-1\)次多项式

形象点说就是\(x^n - y^n = (x-y)\sum{x^ky^{n-1-k}}\)

设\(f(n,j)\)是\(p(n)\) 次多项式 那么

等式左边是 \(p(n)-1\)次多项式 右边是\(p(n-1) + 1\)次多项式

得到\(p(n) = 2n\)

所以\(f\)可以用一个\(2n+1\)次多项式表示出来

所以预处理\(f(n,2n+1)\)范围内的dp值 然后拉格朗日插值即可。

#include<cstdio>
#include<cstring>
const int N = 1e3 + 7;
typedef long long ll;
inline ll fst(ll b, ll k, ll p) {
  ll ans = 1ll;
  while (k) {
    if (k & 1) ans = ans * b % p; b = b * b % p, k >>= 1;
  } return ans;
}
ll lagr (ll *qx, ll *qy, int up, ll x) {
  ll res = 0;
  for (int i = 1; i <= up; i++) {
    ll s1 = 1, s2 = 1;
    for (int j = 1; j <= up; j++) if (i != j) {
      s1 = (ll)(s1 * (x - qx[j]) % mo) % mo;
      s2 = (ll)(s2 * (qx[i] - qx[j]) % mo + mo) % mo; 
    } res = (res + (ll)(s1 * fst(s2, mo - 2, mo) % mo) * qy[i] % mo) % mo;
  } return (res % mo + mo) % mo;
}
ll f[N][N]; int n, m; ll A, mo, fac[N*2], xi[N*2];
int main() {
  scanf ("%lld%d%lld", &A, &n, &mo);
  m = n + n + 1, fac[0] = fac[1] = 1;
  for (int i = 0; i <= m; i++) f[0][i] = 1;
  for (int i = 2; i <= m; i++) fac[i] = (fac[i - 1] * i) % mo;
  for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
    f[i][j] = (ll)((f[i - 1][j - 1] * j) % mo + f[i][j - 1]) % mo;
  for (int i = 0; i <= m; i++) xi[i] = i;
  printf ("%lld", (fac[n] * lagr(xi, f[n], m, A)) % mo);
}

BZOJ 2655 calc

原文：https://www.cnblogs.com/cjc030205/p/11638102.html