「UR #8」宿命多项式

2020 年 10 月 4 日

给定 $n$ 和 $\{c_{i}\}_{i=0}^n$ ，表示 $n+1$ 条限制形如对于 $f(x)$ 满足 $1 \leq f(i) \leq c_i$ 对于所有 $0\le i\le n$ 。

其中 $f(x) = \sum_{i=0}^{n} a_i x^i$ ，这里 $\{a_i\}_{i=0}^n$ 都是整数，即 $f(x)$ 是一个不超过 $n$ 次的整系数多项式。

问满足限制的 $f(x)$ 有多少个，答案对 $998244353$ 取模。

$0\le n\le 6$ ， $1\le c_i\le 10^9$ 。

题解

考虑把 $1 \leq f(i) \leq c_i$ 的限制转换为 $0 \leq f(i) < c_i$ ，且将 $f(x)$ 转化为下降幂多项式。注意到这些转化不会影响到答案。

我们令 $a_i = x_i (n-i)! + y_i$ ，考虑枚举 $y_i$ 后怎么计算答案。

我们提出其中一项式子：

0 \leq a_0 + k a_1 + k^{\underline 2}a_2 + k^{\underline 3} a_3 + \cdots + k! a_k < c_k

把前半部分设为 $d_k$ ，则有：

0 \leq d_k + k!a_k < c_k

代入 $a_k = x_k (n-k)! + y_k$ 得：

0 \leq d_k + k!(x_k (n-k)! + y_k) < c_k

其中 $y_k$ 是我们已经枚举的整数，故只需要考虑对 $x_k$ 计数即可。

-d_k - k! y_k \leq k!(n-k)! x_k < c_k - d_k - k! y_k

答案显然是在 $\frac {c_k} {k!(n-k)!}$ 的级别，但是会有 $\pm 1$ 的偏差，取决于不等式两边在模意义下的大小，具体地（令 $C=d_k+ k!y_k ,\ M = k!(n-k)!$ ）：

\operatorname{count}(x_k)= \begin{cases} \lfloor \frac {c_k} {M} \rfloor & (C \bmod M \leq c_k + C \bmod M) \\ \lfloor \frac {c_k} {M} \rfloor +1 & (C \bmod M > c_k + C \bmod M) \\ \end{cases}

我们现在考察 $C\bmod M$ 的关系， $k!y_k$ 的贡献是已知常数，考虑：

d_k = \sum_{i=0}^{k-1} a_i k^{\underline i} = \sum_{i=0}^{k-1} (x_i(n-i)! + y_i) k^{\underline i}

注意到 $(n-i)!k^{\underline i}$ 是 $M$ 的倍数，故 $C \bmod M$ 只和 $y_{0 \ldots k}$ 有关。

可以通过枚举 $y_{0 \ldots n}$ 后计算，时间复杂度 $O(n \times n! \times (n-1)! \times \cdots \times 1!)$ 。

虽然理论上来说是不能过的但是可以通过巨大多常数优化草过去，实际表现还是跑的挺快的。（竟然比以小常数著名的 zx2003 学长快！）

代码

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#include <bits/stdc++.h>
using namespace std;
const int N = 10, F = 10000, mod = 998244353;
const int fac[N] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
const int ifac[N] = {1, 1, 499122177, 166374059, 291154603, 856826403, 641926577, 376916469, 421456191, 712324701};
const int down[N][N] = {{1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 2, 2, 0, 0, 0, 0, 0, 0, 0}, {1, 3, 6, 6, 0, 0, 0, 0, 0, 0}, {1, 4, 12, 24, 24, 0, 0, 0, 0, 0}, {1, 5, 20, 60, 120, 120, 0, 0, 0, 0}, {1, 6, 30, 120, 360, 720, 720, 0, 0, 0}, {1, 7, 42, 210, 840, 2520, 5040, 5040, 0, 0}, {1, 8, 56, 336, 1680, 6720, 20160, 40320, 40320, 0}, {1, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880}};
int n, q, c[N], d[N], y[N], fit[N][F];
struct z {
  int x;
  z(int x = 0) : x(x) {}
  inline void operator*=(z r) { x = (long long)x * r.x % mod; }
  inline void operator+=(z r) { (x += r.x) >= mod && (x -= mod); }
  friend inline z operator*(z a, z b) { return (long long)a.x * b.x % mod; }
  friend inline z operator-(z a, z b) { return (a.x -= b.x) < 0 ? a.x + mod : a.x; }
  friend inline z operator+(z a, z b) { return (a.x += b.x) >= mod ? a.x - mod : a.x; }
} ans, cur[1 << 7];
void dfs(int u) {
  if (u > n) {
    int x = 0;
    for (int i = 0; i <= n; i++) {
      x |= fit[i][d[i]] << i;
    }
    ans += cur[x];
    return;
  }
  for (int i = 0; i < fac[n - u]; i++) {
    y[u] = i;
    for (int i = u; i <= n; i++) d[i] += y[u] * down[i][u];
    dfs(u + 1);
    for (int i = u; i <= n; i++) d[i] -= y[u] * down[i][u];
  }
}
void mainVI() {
  long long ans = 0;
  y[5] = y[6] = 0;
  for (y[0] = 0; y[0] < fac[6]; y[0]++) {
    for (int i = 0; i <= 6; i++) d[i] += y[0];
    for (y[1] = 0; y[1] < fac[5]; y[1]++) {
      for (int i = 1; i <= 6; i++) d[i] += y[1] * down[i][1];
      for (y[2] = 0; y[2] < fac[4]; y[2]++) {
        for (int i = 2; i <= 6; i++) d[i] += y[2] * down[i][2];
        for (y[3] = 0; y[3] < fac[3]; y[3]++) {
          for (int i = 3; i <= 6; i++) d[i] += y[3] * down[i][3];
          for (y[4] = 0; y[4] < fac[2]; y[4]++) {
            for (int i = 4; i <= 6; i++) d[i] += y[4] * down[i][4];
            int x = 0;
            for (int i = 0; i <= 6; i++) x |= fit[i][d[i]] << i;
            ans += cur[x].x;
            for (int i = 4; i <= 6; i++) d[i] -= y[4] * down[i][4];
          }
          for (int i = 3; i <= 6; i++) d[i] -= y[3] * down[i][3];
        }
        for (int i = 2; i <= 6; i++) d[i] -= y[2] * down[i][2];
      }
      for (int i = 1; i <= 6; i++) d[i] -= y[1] * down[i][1];
    }
    for (int i = 0; i <= 6; i++) d[i] -= y[0];
  }
  ::ans.x = ans % mod;
}
int main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> q; q--; ans = 0) {
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> c[i];
    for (int i = 0; i <= n; i++)
      for (int d = 0; d < F; d++) {
        fit[i][d] = (c[i] + d) % (fac[i] * fac[n - i]) < d % (fac[i] * fac[n - i]);
      }
    for (int x = 0; x < (1 << (n + 1)); x++) {
      cur[x] = 1;
      for (int i = 0; i <= n; i++)
        if ((x >> i) & 1) {
          cur[x] *= c[i] / (fac[i] * fac[n - i]) + 1;
        } else {
          cur[x] *= c[i] / (fac[i] * fac[n - i]);
        }
    }
    (n == 6) ? mainVI() : dfs(0);
    cout << ans.x << endl;
  }
}

题解

代码

评论