2021-7-20acm总结

发表于

A

标签

位运算 + FWTFWT

思路

这道题拓展了我对 FWTFWT 的认识. 没想到 FWTFWT 还能这样玩。

FWTFWT 是一个把位运算数值表达式转化为点值表达式的算法。

对于某些运算，数值表达式转化为点值表达式存在通项公式。

如异或运算，设 gig_i 表示点值，fif_i 表示 ii 次项系数，那么 gi=∑j=0n−1(−1)popcnt(i&j)fjg_i = \sum_{j=0}^{n-1}(-1)^{popcnt(i\&j)} f_j

这道题是给出式子 : bi=∑j=0n−1((popcnt((iorj)xori))+1)mod2)aib_i = \sum_{j=0}^{n-1} ((popcnt((i orj)xori)) + 1) mod 2)a_i

把这个式子乘 22 后再减去 ∑j=0n−1ai\sum_{j=0}^{n-1}a_i， 就是

2×bi+∑j=0n−1ai=∑j=0n−1(−1)popcnt((iorj)xori))+1ai2 \times b_i + \sum_{j=0}^{n-1}a_i = \sum_{j=0}^{n-1}(-1)^{popcnt((i orj)xori)) + 1}a_i

转化成 FWTFWT， 矩阵如下

​ 0 1

0 1 1

1 -1 1

这里我们知道 bib_i ，要求 aia_i ，把矩阵求逆.

​ 0 1

0 12\frac{1}{2} −12-\frac{1}{2}

1 12\frac{1}{2} 12\frac{1}{2}

然后 FWTFWT 一遍就可以了.

还有一个问题，就是我们用来求 aia_i 的是 2×bi+∑j=0n−1ai2 \times b_i + \sum_{j=0}^{n-1}a_i ，∑j=0n−1ai\sum_{j=0}^{n - 1}a_i 我们不知道啊。

但是仔细一想，发现 ∑j=0n−1ai=bn−1\sum_{j=0}^{n - 1}a_i = b_{n-1} ， 于是有 2×bi+bn−12 \times b_i + b_{n-1} ，用这个就可以求出来 aia_i 了.

Code

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
#include <iostream>
#include <cstdio>
#define int long long

using namespace std;

const int N = 3e6 + 10;
int f[N];
int n;
int sum;

signed main() {
  scanf("%lld", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld", &f[i]);
    sum = f[n - 1];
  }
  for (int i = 0; i < n; ++i) {
    f[i] = 2 * f[i] - sum;
  }
  sum = f[n - 1];
  for (int len = 2; len <= n; len <<= 1) {
    int p = len / 2;
    for (int l = 0; l < n; l += len) {
      for (int k = l; k <= l + p - 1; ++k) {
        int tmp = f[k];
        f[k] = (f[k] + f[k + p]) / 2;
        f[k + p] = (-tmp + f[k + p]) / 2;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    printf("%lld ", f[i]);
  }
  return 0;
}

B

标签

后缀自动机

思路

像平时一样，对字符串建一个 SAMSAM ， 但是对于每一个节点，记录一下这个节点 endposendpos 的最小值 minnminn。对于一个插入进去的节点，它的 minnminn 就是这个前缀的右端点。对于一个分裂出来的点，它的 minnminn 等于分裂前节点的 minnminn。证明如下。

对于一个插入进去的节点，它的 endposendpos 集合只有 11， 所以显然成立。

对于一个分裂出来的节点，有两种点。这两种点中的字符串一定是分裂之前点中最长字符串的后缀，分裂之前点中最短字符串一定是这两种点中的字符串的后缀。

查询直接搜就行，一直到不能继续拓展。

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

struct Node {
  int link, ch[27], len, siz, minn;
}tr[4 * N];
char s[N];
int n;
int tot;
int las;
int ans;
int len;

void add(int c, int i) {
  int p = las, np = ++tot;
  las = np;
  tr[np].len = tr[p].len + 1;
  tr[np].minn = i;
  while (p && !tr[p].ch[c]) tr[p].ch[c] = np, p = tr[p].link;
  if (!p) tr[np].link = 1;
  else {
    int v = tr[p].ch[c];
    if (tr[v].len == tr[p].len + 1) tr[np].link = v;
    else {
      int nv = ++tot;
      tr[nv] = tr[v];
      tr[nv].len = tr[p].len + 1;
      while (p && tr[p].ch[c] == v) tr[p].ch[c] = nv, p = tr[p].link;
      tr[np].link = tr[v].link = nv;
    }
  }
}

void query(int i) {
  len = 0;
  ans = 0;
  int u = 1;
  for (int j = i; j <= n; ++j) {
    if (!tr[u].ch[s[j] - 'a' + 1] || tr[tr[u].ch[s[j] - 'a' + 1]].minn >= j) break;
    ++len;
    u = tr[u].ch[s[j] - 'a' + 1];
    ans = tr[u].minn - len + 1;
  }
}

int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  las = tot = 1;
  for (int i = 1; i <= n; ++i) {
    add(s[i] - 'a' + 1, i);
  }
  for (int i = 1; i <= n;) {
    ans = 0;
    query(i);
    if (!ans) {
      printf("-1 %d ", s[i]); 
      ++i;
    }
    else {
      printf("%d %d ", len, ans - 1);
      i = i + len;
    }
  }
  return 0;
}

总结

在 SAMSAM 上，一个点被拆成两个点，拆成的两个点的 endposendpos 最小值等于原来点的 endposendpos 最小值.

猛然发现

自己把这道题搞复杂了，其实一个点 endposendpos 的最小值就是子节点的 endposendpos 最小值的最小值。

C

E

Code

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long

using namespace std;

const int N = 3e6 + 20;
const int mod = 1e9 + 7;
int inv[N], fac[N], ifac[N];
int n, m, k; 
int pos[N], s[N];
int ans1, ans;
int f[N];
int vis[N], t;
int cho[N];
int kno[N], sc[N];
vector<int> has[N];
vector<int> lim;

int C(int n, int m) {
  if (n < 0) return 0;
  if (n < m) return 0;
  return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int solve() {
  for (int i = 1; i <= t; ++i) {
    if (cho[i]) {
      s[pos[kno[i]]] -= sc[i] + 1;
    }
  }
  int res = ans1;
  for (auto i : lim) {
    res = res * C(s[i] + has[i].size() - 1, has[i].size() - 1) % mod;
  }
  for (int i = 1; i <= t; ++i) {
    if (cho[i]) {
      s[pos[kno[i]]] += sc[i] + 1;
    }
  }
  return res;
}

void dfs(int step, int chose) {
  if (step == t + 1) {
    f[chose] = (f[chose] + solve()) % mod;
    return ;
  }
  dfs(step + 1, chose);
  cho[step] = 1;
  dfs(step + 1, chose + 1);
  cho[step] = 0;
}

signed main() {
  scanf("%lld%lld", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int x;
    scanf("%lld", &k);
    for (int j = 1; j <= k; ++j) {
      scanf("%lld", &x);	
      has[i].push_back(x);
      pos[x] = i;
    }
    scanf("%lld", &s[i]);
  }
  scanf("%lld", &t);
  for (int i = 1; i <= t; ++i) {
    scanf("%lld%lld", &kno[i], &sc[i]);
    vis[pos[kno[i]]] = 1;
  }
  fac[0] = ifac[0] = fac[1] = ifac[1] = 1, inv[1] = 1;
  for (int i = 2; i <= N - 10; ++i) {
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[i] = fac[i - 1] * i % mod;
    ifac[i] = ifac[i - 1] * inv[i] % mod;
  }
  ans1 = 1;
  for (int i = 1; i <= m; ++i) {
    if (!vis[i]) {
      ans1 = ans1 * C(s[i] + has[i].size() - 1, has[i].size() - 1) % mod;
    }
    else {
      lim.push_back(i);
    }
  }
  dfs(1, 0);
  for (int i = 0; i <= t; ++i) {
    if (i & 1) {
      ans = (ans - f[i] + mod) % mod;
    }
    else {
      ans = (ans + f[i]) % mod;
    }
  }
  cout << ans << endl;
  return 0;
}