danihao123's Blog

付公主有一个大小为\(10^5\)的背包。然你有\(n\)种类型的物品，其中第\(i\)种体积为\(V_i\)（是正整数），数量有\(10^5\)件。然后给出一正整数\(m\)，对任意\(i=1\ldots m\)求出包里恰好装了\(i\)体积的物品的方案数，答案对\(998244353\)取模。

\(1\leq n\leq 10^5, m\leq 10^5, V_i\leq m\)。

求\(\sum_{i = 0}^n\sum_{j = 0}^i \begin{Bmatrix}i\\ j\end{Bmatrix}2^jj!\)。

\(1\leq n\leq 10^5\)。

给你一个集合\(S\)（保证其中元素都为小于\(n\)的自然数），定义一棵合法的树为一棵编号满足堆的性质，且非叶子节点都一定有两个可能非叶子的儿子，同时有\(c(c\in S)\)个一定为叶子的儿子。对于所有\(i = 1\ldots n\)，求有多少大小为\(i\)的形态不同的合法的树。

\(n\leq 200000\)。

定义分拆数\(f(x)\)表示将\(x\)拆为若干正整数的本质不同方案数。对于\(i = 1\ldots n\)，输出\(f(i)\)。

\(1\leq n\leq 10^5\)。

给你一个大小为\(n\)的集合\({c_1, c_2,\ldots ,c_n}\)，规定合法的二叉树为带点权且点权都属于给定集合中的点的数。对于任意整数$i\in [1, m]$，求出有多少不同的点权和为\(i\)的二叉树并输出之。

\(1\leq n, m, c_i\leq 10^5\)。

aji多项式求逆毁我青春，，，

设\(f_i\)表示\(i\)个点的有标号无向联通图，考虑所有可能的图（记\(F_i\)为\(i\)个点的有标号无向图，显然\(F_i = 2^{\binom{i}{2}}\)）和\(f\)的关系（使用图计数的经典套路：枚举1所在的联通块大小）：

\[F_n = \sum_{i = 1}^n \binom{n-1}{i-1} f_i F_{n - i}\]

看起来事卷积？但是这个卷积没有办法直接用FFT/NTT求（当然分离一下项啊，移下项就可以分治NTT力）。

考虑进一步化简柿子。完全展开后会发现右边有个非常碍眼的\((n-1)!\)，所以两边除一下：

\[\frac{F_n}{(n-1)!} =\sum_{i = 1}^n \frac{f_i}{(i-1)!}\cdot \frac{F_{n - i}}{(n - i)!}\]

然后这个问题就很毒瘤了：我们要求的答案多项式（除上那个阶乘）和一个已知多项式做卷积，可以得到另一个已知多项式……这样就需要多项式除法了，于是乎多项式逆元派上了用场。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 1020010;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a % ha;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x,  ha - 2LL);
}
 
int flip(int bi, int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans += (1 << (bi - i - 1));
    }
  }
  return ans;
}
void NTT(ll *A, int bi, bool flag = false) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int v = flip(bi, i);
    if(v < i) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    ll xi = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi = inv(xi);
    for(int i = 0; i < n; i += (L << 1)) {
      ll w = 1LL;
      for(int j = i; j < i + L; j ++) {
        ll v1 = A[j], v2 = A[j + L];
        A[j] = (v1 + (w * v2) % ha) % ha;
        A[j + L] = (v1 - (w * v2) % ha + ha) % ha;
        w = (w * xi) % ha;
      }
    }
  }
}
void poly_mul(ll *A, ll *B, int bi, ll *C) {
  static ll T1[maxn], T2[maxn];
  int n = (1 << bi);
  std::copy(A, A + n, T1);
  std::copy(B, B + n, T2);
  NTT(T1, bi); NTT(T2, bi);
#ifdef LOCAL
  puts("poly_mul :");
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", A[i]);
  }
  puts("");
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", B[i]);
  }
  puts("");
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", T1[i]);
  }
  puts("");
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", T2[i]);
  }
  puts("");
#endif 
  for(int i = 0; i < n; i ++) {
    T1[i] = (T1[i] * T2[i]) % ha;
  }
#ifdef LOCAL
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", T1[i]);
  }
  puts("");
#endif 
  NTT(T1, bi, true);
  ll inv_n = inv(n);
  for(int i = 0; i < n; i ++) {
    T1[i] = (T1[i] * inv_n) % ha;
  }
  std::copy(T1, T1 + n, C);
#ifdef LOCAL
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", C[i]);
  }
  puts("");
#endif 
}
 
void poly_inv(int mod, ll *B, ll *BB) {
  if(mod == 1) {
    BB[0] = inv(B[0]);
  } else {
    poly_inv((mod + 1) >> 1, B, BB);
    int bi = 0, sz = 1;
    while(sz <= ((mod * 2) + 1)) {
      bi ++; sz <<= 1;
    }
    ll inv_sz = inv(sz);
    static ll tmp[maxn];
    std::copy(B, B + mod, tmp);
    std::fill(tmp + mod, tmp + sz, 0LL);
    NTT(tmp, bi); NTT(BB, bi);
    for(int i = 0; i < sz; i ++) {
      tmp[i] = (tmp[i] * BB[i]) % ha;
      tmp[i] = (tmp[i] * (ha - 1LL)) % ha;
      tmp[i] = (tmp[i] + 2LL) % ha;
      tmp[i] = (tmp[i] * BB[i]) % ha;
    }
    NTT(tmp, bi, true);
    for(int i = 0; i < sz; i ++) {
      tmp[i] = (tmp[i] * inv_sz) % ha;
    }
    std::copy(tmp, tmp + mod, BB);
    std::fill(BB + mod, BB + sz, 0LL);
  }
}
 
int main() {
  static ll fac[maxn], A[maxn], B[maxn], BB[maxn];
  int n; scanf("%d", &n);
  int bi = 0, sz = 1;
  while(sz <= n + 1) {
    bi ++; sz <<= 1;
  }
  fac[0] = 1LL;
  for(int i = 1; i <= n; i ++) {
    fac[i] = (fac[i - 1] * (ll(i))) % ha;
  }
  B[0] = 1LL;
  for(int i = 1; i <= n; i ++) {
    B[i] = pow_mod(2LL, (ll(i)) * (ll(i - 1)) / 2LL);
    B[i] = (B[i] * inv(fac[i])) % ha;
  }
  for(int i = 1; i <= n; i ++) {
    A[i] = pow_mod(2LL, (ll(i)) * (ll(i - 1)) / 2LL);
    A[i] = (A[i] * inv(fac[i - 1])) % ha;
  }
  poly_inv(n + 1, B, BB);
  poly_mul(A, BB, bi, A);
  printf("%lld\n", (A[n] * fac[n - 1]) % ha);
  return 0;
}

统计的时候，考虑每个店对每个图的贡献，可以看出答案是：

\[n2^{\tfrac{(n - 1)(n - 2)}{2}}\,\sum_{i = 0}^{n - 1} \binom{n - 1}{i} i^k\]

求和号前面还好说，主要看求和号后面的咋搞。

后面的那一部分是个经典题吧……但我还是来推导一番吧：

\[
\begin{aligned}
\sum_{i = 0}^{m} \binom{m}{i} i^k&= \sum_{i = 0}^{m} \binom{m}{i}\sum_{j = 0}^k S(k, j) j!\binom{i}{j}\\
&= \sum_{j = 0}^k S(k, j) j! \sum_{i = 0}^m \binom{m}{i}\binom{i}{j} \\
&= \sum_{j = 0}^k S(k, j) m^{\underline{j}} \sum_{i = 0}^{m} \binom{n - j}{i - j} \\
&= \sum_{j = 0}^k S(k, j) m^{\underline{j}} 2^{m - j}
\end{aligned}
\]

然后如果我们能高效的求出某一行的第二类斯特林数，那么问题就迎刃而解了。

考虑斯特林反演（这本质上是一个容斥，用二项式反演也可以推导）：

\[S(k, j) = \sum_{i = 0}^j \frac{(-1)^{j - i}}{(j - i)!} \cdot \frac{i^k}{i!}\]

这个东西很显然是一个卷积……而且模数还很友好（UOJ模数），用NTT求出一行的第二类斯特林数即可。

代码：

/**************************************************************
    Problem: 5093
    User: danihao123
    Language: C++
    Result: Accepted
    Time:22632 ms
    Memory:25824 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 998244353LL;
const ll bs = 3LL;
inline ll pow_mod(const ll &a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
inline ll inv(const ll &x) {
  return pow_mod(x, ha - 2LL);
}
 
inline int flip(const int &bi, const int &x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans |= (1 << (bi - i - 1));
    }
  }
  return ans;
}
inline void ntt(ll *A, const int &bi, const int &len, bool flag = false) {
  for(int i = 0; i < len; i ++) {
    int v = flip(bi, i);
    if(v < i) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < len; L <<= 1) {
    ll xi = pow_mod(bs, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi = inv(xi);
    for(int i = 0; i < len; i += (L << 1)) {
      ll w = 1LL;
      for(int j = i; j < i + L; j ++) {
        ll x = A[j], y = A[j + L];
        A[j] = (x + (w * y) % ha) % ha;
        A[j + L] = (x - (w * y) % ha + ha) % ha;
        w = (w * xi) % ha;
      }
    }
  }
}
 
const int maxn = 800005;
ll A[maxn], B[maxn];
ll fac[maxn], down[maxn];
int main() {
  ll n; int k; scanf("%lld%d", &n, &k);
  if(n == 1) {
    puts("0"); return 0;
  }
  int len = 1, bi = 0;
  while(len <= (2 * k)) {
    len <<= 1; bi ++;
  }
  fac[0] = 1LL;
  for(int i = 1; i <= k; i ++) {
    fac[i] = (fac[i - 1] * (ll(i))) % ha;
  }
  for(int i = 0; i <= k; i ++) {
    A[i] = (inv(fac[i]) * pow_mod(ha - 1LL, i)) % ha;
  }
  for(int i = 0; i <= k; i ++) {
    B[i] = inv(fac[i]);
    B[i] = (B[i] * pow_mod(i, k)) % ha;
  }
  ntt(A, bi, len); ntt(B, bi, len);
  for(int i = 0; i < len; i ++) {
    A[i] = (A[i] * B[i]) % ha;
  }
  ntt(A, bi, len, true);
  ll inv_l = inv(len);
  for(int i = 0; i < len; i ++) {
    A[i] = (A[i] * inv_l) % ha;
  }
#ifdef LOCAL
  for(int i = 0; i <= k; i ++) {
    printf("%lld ", A[i]);
  }
  puts("");
#endif
  down[0] = 1LL;
  for(int i = 1; i <= std::min(ll(k), n - 1LL); i ++) {
    down[i] = (down[i - 1] * (n - (ll(i)))) % ha;
  }
  ll ans = 0LL;
  for(int i = 1; i <= std::min(ll(k), n - 1LL); i ++) {
    ll delta = (A[i] * down[i]) % ha;
    delta = (delta * pow_mod(2, n - 1LL - (ll(i)))) % ha;
    ans = (ans + delta) % ha;
  }
  ans = (ans * pow_mod(2LL, (n - 1LL) * (n - 2LL) / 2LL)) % ha;
  ans = (ans * n) % ha;
  printf("%lld\n", ans);
  return 0;
}

终于调过去了……（然而不就是道NTT+生成函数水题吗至于调半天）

首先积非常的恶心，考虑转成和。这个事需要求指标的……求指标的话枚举原根的若干次幂即可（恰好$m$是素数一定有原根……），判断原根用比较大力的手段即可（我搞了一个$O(n\sqrt{n}logn)$的……求轻喷）。

然后这题还算比较简单吧……用生成函数表示原来的集合，然后$n$次幂就可以了。

注意那事个循环卷积……所以要开两倍然后每次乘完了再把右半部分搞过去。

代码：

/**************************************************************
    Problem: 3992
    User: danihao123
    Language: C++
    Result: Accepted
    Time:6652 ms
    Memory:1864 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <cmath>
typedef long long ll;
const int maxn = 32005;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll n, m, gl; int sz;
ll pow_mod(ll a, ll b, ll p) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b >> 1, p);
  ans = (ans * ans) % p;
  if(b & 1LL) ans = (ans * a) % p;
  return ans;
}
ll inv(ll x, ll p) {
  return pow_mod(x, p - 2LL, p);
}
void break_up(ll x, std::vector<ll> &V) {
  int bd = sqrt(x + 0.5);
  for(ll i = 2; i <= bd; i ++) {
    if(x % i == 0) {
      V.push_back(i);
      while(x % i == 0) x /= i;
    }
    if(x == 1LL) break;
  }
  if(x > 1LL) V.push_back(x);
}
ll get_phi() {
  if(m == 2LL) return 1LL;
  ll mi = m - 1LL;
  std::vector<ll> V;
  break_up(mi, V);
  for(ll i = 2; i <= mi; i ++) {
    bool ok = true;
    for(int j = 0; j < V.size(); j ++) {
      ll b = mi / V[j];
      if(pow_mod(i, b, m) == 1LL) {
        ok = false;
#ifdef LOCAL
        printf("%lld not passed!\n", i);
#endif
        break;
      }
    }
    if(ok) {
      return i;
    }
  }
}
 
int bi, len;
int flip(int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans += (1 << (bi - i - 1));
    }
  }
  return ans;
}
void ntt(ll *A, bool flag = false) {
  for(int i = 0; i < len; i ++) {
    int v = flip(i);
    if(v < i) std::swap(A[i], A[v]);
  }
  for(int L = 1; L < len; L <<= 1) {
    ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)), ha);
    if(flag) xi_n = inv(xi_n, ha);
    for(int i = 0; i < len; i += (L << 1)) {
      ll w = 1;
      for(int j = i; j < i + L; j ++) {
        ll p1 = A[j], p2 = A[j + L];
        A[j] = (p1 + (p2 * w) % ha) % ha;
        A[j + L] = (p1 - (p2 * w) % ha + ha) % ha;
        w = (w * xi_n) % ha;
      }
    }
  }
}
void poly_mul(ll *A, ll *B) {
  static ll C[maxn]; memset(C, 0, sizeof(C));
#ifdef LOCAL
  printf("A :");
  for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
  puts("");
  printf("B :");
  for(int i = 0; i < len; i ++) printf(" %lld", B[i]);
  puts("");
#endif
  ntt(A); ntt(B);
  for(int i = 0; i < len; i ++) C[i] = (A[i] * B[i]) % ha;
  ntt(C, true);
  ll inv_n = inv(len, ha);
  for(int i = 0; i < len; i ++) {
    C[i] = (C[i] * inv_n) % ha;
  }
#ifdef LOCAL
  printf("C (not processed) :");
  for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
  puts("");
#endif
  for(int i = 0; i < len; i ++) {
    int v = i % (m - 1LL);
    if(v != i) {
      C[v] = (C[v] + C[i]) % ha;
      C[i] = 0LL;
    }
  }
#ifdef LOCAL
  printf("C :");
  for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
  puts("");
#endif
  std::copy(C, C + len, A);
}
void poly_pow(ll *A, ll b) {
  static ll B[maxn];
  static ll res[maxn];
  std::copy(A, A + len, res);
  std::fill(A, A + len, 0); A[0] = 1LL;
#ifdef LOCAL
  printf("A :");
  for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
  puts("");
  printf("res : ");
  for(int i = 0; i < len; i ++) printf("%lld ", res[i]);
  puts("");
#endif
  while(b) {
    if(1LL & b) {
      std::copy(res, res + len, B);
      poly_mul(A, B);
      std::fill(B, B + len, 0);
    }
    std::copy(res, res + len, B);
    poly_mul(res, B);
    std::fill(B, B + len, 0);
    b >>= 1LL;
  }
}
 
int main() {
  static bool vis[maxn];
  static ll A[maxn];
  scanf("%lld%lld%lld%d", &n, &m, &gl, &sz);
  ll phi = get_phi();
  for(int i = 1; i <= sz; i ++) {
    int v; scanf("%d", &v);
    if(v == 0) continue;
    vis[v] = true;
  }
  int logx = 0;
  bi = 0; len = 1;
  while(len <= (2 * m - 2)) {
    bi ++; len <<= 1;
  }
  for(int i = 0; i < (m - 1); i ++) {
    int v = pow_mod(phi, i, m);
    if(vis[v]) {
      A[i] ++;
#ifdef LOCAL
      printf("log(%d) : %d\n", v, i);
#endif
    }
    if(v == gl) {
      logx = i;
    }
  }
  poly_pow(A, n);
  printf("%lld\n", A[logx]);
  return 0;
}