Atcoder abc212

發表於 更新於 分類於 ， 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