[NOI Online#3]优秀子序列 [集合幂级数exp]

[NOI Online#3]优秀子序列

首先易知i \And j=0等价于i | j = i +j。于是就是子集卷积。O(3^n)卷一下就行了。注意特判0考场代码不知道为什么60分

考虑使用形式幂级数。冷静分析一下:首先一个数不能选两次,因此随便选k次,除以k!,就得到了k个数的方案数。可以发现k \leq n

答案写出来就是G(x) = 1 + \sum_{i \geq 1} \frac{F(x)^i}{i!},发现这玩意和e^{F(x)}一模一样。于是\exp就好了。

注意到n非常小,直接考虑暴力\expB=e^A \rightarrow B' = A' e^A \rightarrow B = \int A'B

#include <bits/stdc++.h>

using std::cerr;
using std::endl;

inline int rd() {
  int b = 0; char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return b;
}

const int N = 3e5 + 10, P = 1e9 + 7, lim = 1 << 18, L = 18;

inline void check(int &x) {
  x -= P, x += x < 0 ? P : 0;
}

int n, A[N], pr[N], tot, vis[N], phi[N], inv[N];

inline void init() {
  phi[1] = inv[1] = 1;
  for (int i = 2; i <= lim; ++i) {
    check(inv[i] = P - 1ll * P / i * inv[P % i] % P);
    if (!vis[i]) {
      pr[++tot] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= tot && i * pr[j] <= lim; ++j) {
      vis[i * pr[j]] = 1;
      if (!(i % pr[j])) {
        phi[i * pr[j]] = phi[i] * pr[j];
        break;
      }
      phi[i * pr[j]] = phi[i] * phi[pr[j]];
    }
  }
}

inline void fwt(int f[], int o) {
  for (int i = 1; i < lim; i <<= 1)
    for (int j = 0; j < lim; j += i << 1)
      for (int k = 0; k < i; ++k)
        o == 1 ? check(f[i + j + k] += f[j + k]) : check(f[i + j + k] += P - f[j + k]);
}

int f[L + 1][N], g[L + 1][N], ans;

inline void solve() {
  for (int i = 1; i < lim; ++i)
    f[__builtin_popcount(i)][i] = A[i];
  for (int i = 1; i <= L; ++i) {
    fwt(f[i], 1);
    for (int j = 0; j < lim; ++j)
      f[i][j] = 1ll * f[i][j] * i % P;
  }
  for (int i = 0; i < lim; ++i) {
    g[0][i] = 1;
    for (int j = 1; j <= L; ++j) {
      int tmp = 0;
      for (int k = 1; k <= j; ++k)
        tmp = (tmp + 1ll * f[k][i] * g[j - k][i]) % P;
      g[j][i] = 1ll * tmp * inv[j] % P;
    }
  }
  for (int i = 0; i <= L; ++i)
    fwt(g[i], -1);
  for (int i = 0; i < lim; ++i)
    ans = (ans + 1ll * g[__builtin_popcount(i)][i] * phi[i + 1]) % P;
  for (int i = 1; i <= A[0]; ++i)
    ans = ans * 2 % P;
  std::cout << ans << std::endl;
}

int main() {
  n = rd();
  for (int i = 1; i <= n; ++i)
    ++A[rd()];
  init(), solve();
  return 0;
}

发表评论

电子邮件地址不会被公开。必填项已用 * 标注