「UR #8」宿��命多项式
「UR #8」宿命多项式

2020 年 10 月 04 日

给定 nnc0nc_{0\ldots n},表示限制形如对于 0in0 \leq i \leq n 都满足 1f(i)ci1 \leq f(i) \leq c_i

其中 f(x)=i=0naixif(x) = \sum_{i=0}^{n} a_i x^i,其中 a0na_{0 \ldots n} 都是整数,即 f(x)f(x) 是一个不超过 nn 次的整系数多项式。

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

题解

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

我们令 ai=xi(ni)!+yia_i = x_i (n-i)! + y_i,考虑枚举 yiy_i 后怎么计算答案。

我们提出其中一项式子:

0a0+ka1+k2a2+k3a3++k!ak<ck0 \leq a_0 + k a_1 + k^{\underline 2}a_2 + k^{\underline 3} a_3 + \cdots + k! a_k < c_k

把前半部分设为 dkd_k,则有:

0dk+k!ak<ck0 \leq d_k + k!a_k < c_k

代入 ak=xk(nk)!+yka_k = x_k (n-k)! + y_k 得:

0dk+k!(xk(nk)!+yk)<ck0 \leq d_k + k!(x_k (n-k)! + y_k) < c_k

其中 yky_k 是我们已经枚举的整数,故只需要考虑对 xkx_k 计数即可。

dkk!ykk!(nk)!xk<ckdkk!yk-d_k - k! y_k \leq k!(n-k)! x_k < c_k - d_k - k! y_k

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

count(xk)={ckM(CmodMck+CmodM)ckM+1(CmodM>ck+CmodM)\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}

我们现在考察 CmodMC\bmod M 的关系,k!ykk!y_k 的贡献是已知常数,考虑:

dk=i=0k1aiki=i=0k1(xi(ni)!+yi)kid_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}

注意到 (ni)!ki(n-i)!k^{\underline i}MM 的倍数,故 CmodMC \bmod M 只和 y0ky_{0 \ldots k} 有关。

可以通过枚举 y0ny_{0 \ldots n} 后计算,时间复杂度 O(n×n!×(n1)!××1!)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;
  }
}

评论

TABLE OF CONTENTS

题解