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$非常小，直接考虑暴力$\exp$。$B=e^A \rightarrow B’ = A’ e^A \rightarrow B = \int A’B$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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;
}