YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 1.8k 所需閱讀時間 ≈ 6 分鐘
G(DP, 字符串),H/Ex(图,DP,拓扑排序,dij,拆点)

G - Replace

字符串S,T包含小写英文

可以执行k种 操作, 任意次 任意顺序

第i种 操作: 1代价, 把一个字符Ci 换成 字符串Ai

问S变成T 的最小代价 或不可能

限制

|S|<=|T| <= 50

k <= 50

|Ai| <= 50

2s

1024mb

题解

我的思路

既然是字符(离散)换成字符串

那么岂不是 dp[i][j] 表示 S前i 个换成 T前j个

dp[i][j] = dp[i-1][j-k], s[i] -> T[j-k+1..j] 可行

那么问题是如何判断可行

换句话说, 如果我们能算出 T[j-k+1..j] 能否逆向变成s[i] 也是办法

但是感觉这个会分叉很多

题解

dp[i][j][c] = 最小代价T[i..j] => 字符 c

f[i][j][k][l] = 最小代价T[i..j] => 字符串 A[k][1..l] (这个很关键, 是把字符中前缀设置成状态)

1
2
3
for i = N -> 1:
  for j = i -> N:
    计算 f[i][j][k][l], f[i][j][c], f[i][j][k][1]

计算f[i][j][k][l] 时 (T[i..j] => A[k][1..l])

注意到替换时顺序不会变相当于

时 (T[i.m][m+1.j] => A[k][1..l-1] A[k][l])

$f[i][j][k][l] = min(f[i][m][k][l-1] + dp[m+1][j][A[k][l]])$

计算dp[i][j][c] / f[i][j][k][1]

  1. 本身就是c字符, i==j, Ti = c, 0
  2. 一步到位 T[i..j] = A[k], C[k] = c
  3. 先转换到某个A[k] 再转一步, min(f[i][j][k][|A[k]|]+1),C[k] = c

f[i][j][k][1] 从dp[i][j][A[k][1]] 中读即可

这大概是O(n^4)的状态

O(n^5) 的转移复杂度

这其中还有一个问题是, 对于A和C都是单个字符的, 你会出现T[i...j] -> c0 -> c1 -> c2

你需要求最短路dij/spfa松弛 即可

代码

https://atcoder.jp/contests/abc261/submissions/33608140

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
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;} // read

const int INF = 0x3f3f3f3f; // 无穷大
const int maxc = 'z' - 'a'; // 最大字符对应数字

vector<int> t;
int f[60][60][60][60]; // [l..r] => a[k][0...i] (prefix(a[k][i]))
int dp[60][60][30]; // [l..r] => char c

int c[60] = {maxc + 1}; // 不存在的字符
vector<int> a[60]; // c[i] -> a[i];
vector<pair<int,int> > c2c; // 单字符映射

char tmp[60];
int lcStr2VecInt(vector<int> & res){ // lower case string to vector<int>
  scanf("%s", tmp);
  int sz = strlen(tmp);
  res.resize(sz);
  rep(i,0,sz) res[i] = tmp[i] - 'a'; // s 放在 c[0],a[0]
  return sz;
}

void setMin(int &v0,int v1){v0 = min(v0,v1);}

int main(){
  int ns = lcStr2VecInt(a[0]); // s 放在 c[0],a[0]
  int nt = lcStr2VecInt(t); // t
  int K = read() + 1; // 包含s
  rep(i,1,K){
    scanf("%s", tmp);
    c[i] = tmp[0] - 'a';
    if(lcStr2VecInt(a[i]) == 1) c2c.push_back({c[i], a[i][0]});
  }
  rep(l,0,nt) {
    rep(r,l,nt) { // 全部设置为无穷大
      rep(k,0,K) rep(i,0,50) f[l][r][k][i] = INF;
      rep(c,0,maxc+1) dp[l][r][c] = INF;
    }
    dp[l][l][t[l]] = 0; // 本身就是字符
  }
  // --- init ---
  per(l,0,nt) rep(r,l,nt){ // T[l..r], 各种顺序都行 保证依赖关系先被运算
    rep(k,0,K){
      int sz = a[k].size();
      rep(i,1,sz){ // T[l..j][j+1..r] = > a[k][0..i-1],a[k][i]
        int &v = f[l][r][k][i];
        rep(j,l,r) setMin(v, f[l][j][k][i-1] + dp[j+1][r][a[k][i]]);
        if(i == sz - 1) setMin(dp[l][r][c[k]], v + 1); // T[i..j] => a[k] => c[k]
      }
    }
    // dp[l][r][c]=min(dp[l][r][k][|a[k]|]) + 1 = min(len > 1(上面算了), len = 1) + 1, len = |a[k]|
    rep(c,0,maxc+1) for(auto [c0, c1]: c2c) setMin(dp[l][r][c0], dp[l][r][c1] + 1); // 26 次 松弛
    rep(k,0,K) setMin(f[l][r][k][0], dp[l][r][a[k][0]]); // 更新 f 中首字母
  }
  int & ans = f[0][nt-1][0][ns-1];
  printf("%d\n", ans == INF? -1: ans);
  return 0;
}


H/Ex - Game on Graph

N点, M边

有向边 [ui,vi,weight i], 无重边 无自环

初始,点v上有个棋子

T和A交替游戏

  • 如果棋子所在点 没有向外路径 则结束游戏
  • 如果有路径,任选一个走路径

T 让weight和尽量小, A让和尽量大

T(结束游戏优先级 > 和尽量小)

A(让游戏无限循环优先级 > 和尽量大)

限制

N 2e5

M 2e5

Wi [0,1e9]

2s

1024mb

题解

我的思路

并不是有环就一定无限, 例如 a->b->c->d->a

a连了个有限的, c也连了个更短的有限的

那么虽然你可以走到b,让对手走到c,这样在走到有限的 会比a直接去到有限的更短

考虑从叶子反过来, 判断是否有限,感觉bfs或者spfa/dij的感觉

题解

图上环状dp

dp[x][0] 从x出发 尽量小

dp[x][1] 从x出发 尽量大

dp[x][0] = min (f[y][1] + weight[x][y]), 相当于 反向图的最短路

dp[x][1] = max (f[y][0] + weight[x][y]), 需要所有f[y][0] 被计算后才有意义

然后就反图+拓扑+dij 就没了???

我感觉这个条件必要, 但总觉得没有证明到充分

代码

https://atcoder.jp/contests/abc261/submissions/33603896

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
ll dp[2][200010];
ll mx[200010]; // 只记录1的, 因为0的直接记录在pq和dp中, 而1的在子节点未完全计算时pq和dp都不会记录
int deg[200010]; // 正向图出度, 反向图入度
vector<pair<int,int> > g[200010]; // 反向图 v = {u, weight}
 
template <typename T> using minPQ = priority_queue<T,vector<T>, greater<T>>; // 小根堆
 
int main(){
  int n = read();
  int m = read();
  int v = read();// 起点
  rep(i,0,2) fill(dp[i],dp[i]+n+1,-1); // 未访问
  rep(i,0,m) {
    int u = read();
    int v = read();
    int w = read();
    g[v].push_back({u, w});
    deg[u] ++;
  }
  minPQ<array<ll,3>> q; // 小根堆, dij 每次找最小的未达点变为可达 {距离, 0/1, 点}
  rep(i,1,n+1) if(deg[i] == 0) rep(j,0,2) q.push({0, j, i}); // dp[0/1][i] 反向入度为0 的节点
  while(q.size()) {
    auto [d, i, u] = q.top(); q.pop();
    if(dp[i][u] != -1) continue; // 计算过
    dp[i][u] = d; // 更新值
    if(!i) { // dp[0][u] -> dp[1][v]
      for(auto [v, w] : g[u]) { // 更新反向边 并更新 deg[v] --
        mx[v] = max(mx[v], d + w); // 更新值但是 不一定进入pq dp[x][1] = max (f[y][0] + weight[x][y])
        if(--deg[v] == 0) q.push({mx[v], 1, v}); // dp[1][v] 只能所有计算都计算后才有意义
      }
    } else for(auto [v, w] : g[u]) q.push({d + w, 0, v}); // dp[1][u] -> dp[0][v] dij
  }
  if(dp[0][v] == -1) printf("INFINITY\n");
  else printf("%lld\n", dp[0][v]);
  return 0;
}

总结

G

大小只有50的情况, 对字符串中的前缀设计状态, 从而有dp的状态

第二就是 小的情况 多次松弛简单也效率满足, 不需要上dij

H/Ex

我感觉这个条件必要, 但总觉得没有证明到充分???

可能关键在于,虽然点上有 0/1两个状态,但实际上这两个状态不相关, 所以其实每个点可以拆点

这样就变成了路径的逆向dp了, 有环一定不行, 所以关键在这个拆点 -> 变成dij

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(SA,后缀数组,单调栈)G(bitmask, 集合论, 图, DP, 子集遍历),H/Ex(DP, 卷积, fft, NTT, 分治NTT)

F - Common Prefixes

题目

https://atcoder.jp/contests/abc213/tasks/abc213_f

给长n字符串S

求其每个位置开始的后缀字符串, 和所有其它后缀字符串的 公共前缀和

范围

n 1e6

3s

1024mb

閱讀全文 »

發表於 更新於 分類於 Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘

相关内容

后缀自动机

最终产物

一个数组sa 记录下标, 按照后缀字典序排序

以及需要的话一个记录rank的数组(和sa相反)

后缀数组

h[i] 表示排名为i的和排名为i-1的最长公共前缀长度

閱讀全文 »

發表於 更新於 分類於 Disqus： 文章字數： 2.8k 所需閱讀時間 ≈ 9 分鐘

FWHT

快速沃尔什-阿达玛转换(Fast Walsh-Hadamard transform), 一种广义傅立叶变换(FWHT)

解决什么问题

FWHT 是用于解决对下标进行位运算卷积问题的方法

$c_{i} = \sum_{i=j \bigoplus k}a_{j} b_{k}$

并且没有fft中会涉及到double

前置知识 FFT(DFT)

DFT:

${\displaystyle {\begin{bmatrix}f_{0}\\
f_{1}\\
\vdots \\
f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\
1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &&\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}.}$

閱讀全文 »

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
G(数学,数论,原根)H/Ex(沃尔什-阿达玛转换,FWT/FWHT)

G - Power Pair

题目

https://atcoder.jp/contests/abc212/tasks/abc212_g

给定 质数$p$

问 $x,y\in[0,p-1]$ 中有多少对$(x,y)$满足

存在$n$, 使得$x^n = y \pmod p$

范围

p $10^{12}$

2s

1024mb

题解

我的思路

显然x=0 只有y = 0, y=0也只有x=0

然后如果x是原根 那么 方案数$p-1$

如果$r|(p-1)$ 那么 $x^r \pmod p$的方案数为$\frac{p-1}{r}$

或者$x$的最小幂次$t$让$x^t = 1 \pmod p$, 则答案为$t$

但是即使这样, 如果每个去枚举依然是$O(p log(p))$

反过来考虑说有没有办法求$x^t = 1$ 的方案数,

如果能快速计算出,那么 方案数减去它的t因子对应的方案数 就恰好是 = t的方案数

而$t$的取值只会是 $p-1$的因数

$t = 1$ $x = 1$

$t = 2$ $x = 1,-1$

$t = 4$

$t = 7$

$t = 8$

t = 2k时, $x^{2k} - 1 = 0 \pmod p$

$(x^k+1)(x^k-1) = 0 \pmod p$, 相当于$x^k = 1 \pmod p, x^k = -1 \pmod p $的解的并

并不会

官方

原根的想法没问题, 然后就变成了我们指定原根

$x^i = j$, $(i,j)$ 是一一对应, 且取$[1,p-1]$范围内的所有值

这样的话

要求 $x^i$ 的最小让 幂次等于1的t

注意到 和我思路一样的 $x^i$当$i | (p-1)$时, 方案数 $=\frac{p-1}{i}$

而这里$i$可能不是$p-1$的因子, 而易证明 方案数为 $\frac{p-1}{gcd(p-1,i)}$

这里问题变成了, 统计不同 $gcd(p-1,i) = k$ 的数量即可

$g | (p-1)$

$\sum_{g|(p-1)} count(g 倍数 且非(p-1)因子) $

代码

https://atcoder.jp/contests/abc212/submissions/33524525

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

// 转质数和幂次
vector<pair<ll,int> > v2ppwr(ll v){
  vector<pair<ll,int> > res = {};
  rep(t,2,v+1){
    if(t*t > v) break;
    int c = 0;
    while(v % t == 0){
      v /= t;
      c ++;
    }
    if(c) res.pb({t,c});
  }
  if(v != 1) res.pb({v, 1});
  return res;
}

// gcd = x
ll dfs(ll idx, ll y, vector<ll> primes, const vector<pair<ll,int> > & ppwr1){
  if(idx == (int)ppwr1.size()) {
    ll rc = y; // 容斥
    for(auto p:primes) rc = rc / p * (p-1);
    return y % MOD * (rc % MOD) % MOD;
  }
  auto [p,mi] = ppwr1[idx];
  ll mul = 1; // p ** pwr
  primes.push_back(p);
  ll res = 0;
  rep(pwr,0,mi+1){
    if(pwr == mi) primes.pop_back();
    (res += dfs(idx+1, y / mul, primes, ppwr1)) %= MOD;
    mul *= p;
  }
  return res;
}

int main(){
  ll p = read();
  auto ppwr = v2ppwr(p-1);
  printf("%lld\n", (1 /* (0,0) */ + dfs(0, p-1, {}, ppwr)) % MOD);
  return 0;
}

H/Ex - Nim Counting

https://atcoder.jp/contests/abc212/tasks/abc212_h

给正整数 长度k的 数组A, 值两两不同

T和A轮流游戏, T先

选一个 >= 1 的石堆, 移除任意正整数个

谁取了最后一个胜利

问题是

对于长度[1,N] 每个元素属于A中的一个的 初始状态, 有多少种状态是 T 胜利

模 998244353

范围

n 2e5

k 65536

$a_i$ [1, 65536]

题解

我的思路

首先nim游戏作为博弈的常见基础, 很明显 就是 xor 和 != 0 时 T胜利

那么无非是求 所有 !=0 的方案数, 或者 是 == 0 的方案数, 去总方案减去 ==0的方案数

那么对于一个选择来说因为Ai两两不同, 偶数次被选的Ai 不影响xor,奇数次被选的Ai影响一次

问题变成了说

选x个Ai,让它们 xor = 0, 那么

对于长度x 贡献是 x!

对长度x+2 贡献是 ?? 还是x, 但是剩余两个是一样的, 这两个一样的如果属于x个值内注意不要重复统计,不属于x个数内,则穿插即可

官方

对于给定的数组长度M

$C=(C_0,C_1,…C_{2^{16}-1})$ 表示 下标的值 是否存在, 相当于选择了一次

定义xor的卷积 $Z_k = \sum_{i\oplus j=k} X_i Y_j$

那么$C$的M次卷积的结果$R$中的$R_0$, 就是期望值

快速沃尔什-阿达玛转换(Fast Walsh Hadamard transform), 一种广义傅立叶变换

FWT/FWHT 是用于解决对下标进行位运算卷积问题的方法, 见下面我的博客链接

$C_{i} = \sum_{i=j \bigoplus k}A_{j} B_{k}$

因为 xor 的卷积满足结合率, 所以可以考虑快速幂来算

注意到$C * C = ifwt(fwt(C)\odot fwt(C))$

而$C * C * C= ifwt(fwt(C * C) \odot fwt(C))$

$= ifwt(fwt(ifwt(fwt(C)\odot fwt(C))) \odot fwt(C))$

$= ifwt(fwt(C)\odot fwt(C) \odot fwt(C))$

即是 $C^n = ifwt(\left( fwt(C)_ i^n\right))$

所以 $C$的$n$次+/xor/or/and卷积等于 正变换每个位置的$n$次方后的逆变换, 这个在dft(fft)/ntt/fwt 同理

令 $I = C^0 = (1,0,0,0,0,0,\cdots)$

答案 $R = C + C * C + \cdots + C^n$

$R * C = C^2 + C^3 + \cdots + C^{n+1}$

$R * (C-I) = C^{n+1} - C$

$fwt(R) \odot fwt(C-I) = fwt(C^{n+1} - C)$

$fwt(R) = fwt(C^{n+1} - C) \oslash fwt(C-I)$

$R = ifwt(fwt(C^{n+1} - C) \oslash fwt(C-I))$

注意到$fwt$ 实际是线性变换, 所以也有$fwt(a+b) = fwt(a) + fwt(b),fwt(a-b) = fwt(a) - fwt(b),$

$R = ifwt( (fwt(C^{n+1}) - fwt(C)) \oslash (fwt(C)-fwt(I)))$

注意到 $fwt(I) = (1,1,1,1,1,\cdots)$

$R = ifwt(\left(\frac{fwt(C)_ i^{n+1} - fwt(C)_ i}{fwt(C)_ i - 1}\right))$

至此就很好写了

代码

https://atcoder.jp/contests/abc212/submissions/33545657

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

// -------------- modint ---------------
namespace MODINT{
  const int _mod = 998244353;
  class modint{
    private:
      ll _v;
    public:
      modint() :_v(0) {  }
      modint(ll _a) {
        _v = (_a < 0)? _mod - ((-_a) % _mod) : (_a % _mod);
      }

      int val()const { return _v; }
      modint operator+()const { return *this; }
      modint operator-()const { return { _mod - _v }; }
      modint operator+(const modint& rhs) const { return modint(*this) += rhs; }
      modint operator-(const modint& rhs) const { return modint(*this) -= rhs; }
      modint operator*(const modint& rhs) const { return modint(*this) *= rhs; }
      modint operator/(const modint& rhs) const { return modint(*this) /= rhs; }

      bool operator==(const modint& rhs)const { return _v == rhs._v; }
      bool operator!=(const modint& rhs)const { return _v != rhs._v; }
      bool operator> (const modint& rhs)const { return _v >  rhs._v; }
      bool operator>=(const modint& rhs)const { return _v >= rhs._v; }
      bool operator<=(const modint& rhs)const { return _v <= rhs._v; }
      bool operator< (const modint& rhs)const { return _v <  rhs._v; }

      modint& operator+=(const modint& rhs) {
        (_v += rhs._v) %= _mod;
        return *this;
      }
      modint& operator-=(const modint& rhs) {
        (_v += _mod - rhs._v) %= _mod;
        return *this;
      }
      modint& operator*=(const modint& rhs) {
        _v = _v * rhs.val() % _mod;
        return *this;
      }
      modint& operator/=(const modint& rhs) { // 费马小定理
        _v = _v * rhs.inv().val() % _mod ;
        return *this;
      }
      modint pow(ll pwr) const {
        ll res(1);
        ll _b(_v);
        while (pwr) {
          if (pwr & 1) (res *= _b) %= _mod;
          (_b *= _b) %= _mod;
          pwr /= 2;
        }
        return res;
      }
      modint inv() const {
        assert(_v != 0);
        return pow(_mod - 2);
      }
  };
};
// -------------- modint ---------------

// ---------- fwt ----------
using MODINT::modint;
namespace FWT{
  void ForT(vector<modint> &f,int flag = 1/* 1:正变换,-1:逆变换 */) {
    int n = f.size();
    for (int k = 1; k < n; k *=2){
      for (int i = 0; i < n; i += 2*k){
        for (int j = 0; j < k; j++){
          f[i+j+k] += f[i+j] * flag;
        }
      }
    }
  }

  void IForT(vector<modint> &f) {ForT(f, -1);}

  vector<modint> or_convolution(vector<modint> &v0, vector<modint> &v1){
    const int sz = v0.size();
    ForT(v0);
    ForT(v1);
    vector<modint> v2(sz,0);
    rep(i,0,sz) v2[i] = v0[i] * v1[i];
    IForT(v2);
    return v2;
  }

  void FandT(vector<modint> &f, int flag = 1/* 1:正变换,-1:逆变换 */) {
    int n = f.size();
    for (int k = 1; k < n; k *=2){
      for (int i = 0; i < n; i += 2*k){
        for (int j = 0; j < k; j++){
          f[i+j] += f[i+j+k] * flag;
        }
      }
    }
  }
  void IFandT(vector<modint> &f) {FandT(f, -1);}

  vector<modint> and_convolution(vector<modint> &v0, vector<modint> &v1){
    const int sz = v0.size();
    FandT(v0);
    FandT(v1);
    vector<modint> v2(sz,0);
    rep(i,0,sz) v2[i] = v0[i] * v1[i];
    IFandT(v2);
    return v2;
  }

  modint inv2 = modint(2).inv();
  void FWHT(vector<modint> &f, modint flag = 1 /* 1: 正变换, 1/2: 逆变换*/) {
    int n = f.size();
    for (int k = 1; k < n; k *=2){
      for (int i = 0; i < n; i += 2*k){
        for (int j = 0; j < k; j++){
          auto U = f[i+j];
          auto T = f[i+j+k];
          f[i+j]   = U + T;
          f[i+j+k] = U - T;
          f[i+j] *= flag;
          f[i+j+k] *= flag;
        }
      }
    }
  }
  void IFWHT(vector<modint> &f) {FWHT(f, inv2);}
  void FxorT(vector<modint> &f,int flag = 1) {FWHT(f, flag);}
  void IFxorT(vector<modint> &f) {IFWHT(f);}

  vector<modint> xor_convolution(vector<modint> &v0, vector<modint> &v1){
    const int sz = v0.size();
    FxorT(v0);
    FxorT(v1);
    vector<modint> v2(sz,0);
    rep(i,0,sz) v2[i] = v0[i] * v1[i];
    IFxorT(v2);
    return v2;
  }
};
// ---------- fwt ----------

const int SIZE = 1 << 16; // 16;
vector<modint> C(SIZE,0);

int main(){
  int n = read();
  int k = read();
  rep(i,0,k) { C[read()] = 1; }
  auto ans = k == 1? n : ((modint(k).pow(n+1)- 1)/(k-1) - 1); // 总方案数
  FWT::FWHT(C);
  rep(i,0,SIZE) C[i] = (C[i] == 1) ? n : ((C[i].pow(n+1) - C[i])/(C[i] - 1)); // 等比数列求和
  FWT::IFWHT(C);
  printf("%d\n",(ans-C[0]).val());
  return 0;
}

总结

G

没观察到选了一个原根以后 整个范围 都有幂次和值的一一映射

H(Ex)

首先这个C和这个卷积 就很神奇, 完全没有向这个方向的思路

学了一手FWT/FWHT

参考

官方题解

FWHT/FWT

0%