后缀数组 SA

發表於 2022-07-27 更新於 2025-06-05 分類於 algorithm Disqus：文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘

最终产物

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

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

后缀数组

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

閱讀全文 »

从FFT 到 FWHT 快速沃尔什-阿达玛转换(Walsh Hadamard transform)

發表於 2022-07-26 更新於 2025-06-05 分類於 algorithm 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}}.}$

閱讀全文 »

Atcoder abc212

發表於 2022-07-25 更新於 2025-06-05 分類於 Atcoder ， ABC 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

#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

#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

从FFT 到 NTT(快速数论变换)

發表於 2022-07-24 更新於 2025-06-05 分類於 algorithm Disqus：文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘

NTT

竟然Div2能出现NTT 虽然是在最后一题, 还是得学一学

解决什么问题

是多项式乘法带模数的情况计算卷积

并且没有fft中会涉及到double,

NTT 也就是关于任意环(数学术语) 上的离散傅立叶变化(DFT), 有限域的情况下,通常成为数论变换

离散傅立叶变换

回顾离散傅立叶变换, 就是

原函数(原向量) $\to$ DFT(离散傅立叶) $\to$ 点乘 $\to$ IDFT(逆傅立叶) $\to$ 结果函数(结果向量)

DFT:

$\hat{x}[k]=\sum_{n=0}^{N-1} e^{-i\frac{2\pi}{N}nk}x[n] \qquad k = 0,1,\ldots,N-1.$

IDFT:

$x\left[n\right]={1 \over N}\sum_{k=0}^{N-1} e^{ i\frac{2\pi}{N}nk}\hat{x}[k] \qquad n = 0,1,\ldots,N-1.$

有时系数可以是两个$\frac{1}{\sqrt{N}}$

矩阵表示的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}}.}$

閱讀全文 »

Educational Codeforces Round 132

發表於 2022-07-23 更新於 2025-06-05 分類於 Codeforces ， Edu Disqus：文章字數： 2.5k 所需閱讀時間 ≈ 8 分鐘

E(树,xor,贪心,树上启发式合并)F(DP,NTT,前缀和)

E

https://codeforces.com/contest/1709/problem/E

给你个一个树, 每个点上有值, 修改尽量少的点为任意值

让任何简单路径的 xor都不为零

范围

n 2e5

ai [1,2^30]

3s

256MB

题解

我的思路

显然啊, 类似树上差分的思想, a…b xor = 0

意味着 a…root ^ root …b = 0

所以直接变成计算每个数到根的xor

然后问题变成, 任意两个相同值之间的连线, 需要至少选一个点

或者说, 需要xor树最终两两不等

不知道往后怎么搞

一个思路是dp

但是遇到同值点不是祖先关系,而是分叉的关系 ,也不知打怎么记录

题解

虽然的确有前缀意义,但其实我想的总思路没问题, 但是细节有问题

并不是简单路径 = 到根的路径 xor

因为它们的lca 被算了两次

所以其实是 path[u]^path[v] = a[lca[u,v]]

那么对于一个点x = lca(u,v) , 且 u..v 的xor = 0

那么 (x,y) 上至少有一点需要改变

然后我们对所有的有这种情况的x 按深度从深到浅考虑

找深度最深的x, 那么修改 x的方案不会比修改 u…v 的更差

因为是最深的, 所以其它满足的链如果经过它的子树则必定经过它,因为它需要修改, 所以而至少一个, 而对于其它经过它的链来说是至多一个

dfs(u){
对于u的所有子树 dfs(v)

每个点获取从根到它的子节点能得到的 xor 集合

一旦有来自两个子树中有值 xor == u 那么u就必然被选
而被选的u对于它的父节点的返回是空集合
未被选的u对于它的父节点的返回是它所有子集合可达值 xor 它自身
}

怎么看都是n^2 啊 , 为啥 O(nlog^2 n)

因为虽然dfs一次就可以把所有点到根的xor 算完

但是每次做 set 的合并时, 一个点就是会在它的父节点中被运算

那每个点被参与比较的次数可以达到链的长度不就是 n^2 吗

然后神奇的是这个启发式合并的复杂度不是n方

启发式合并(DSU on Tree)

oi-wiki 树上启发式合并

重儿子, 儿子节点子节点个数最多的

重边, 当前点连向其中一个重儿子的边

轻边非重边

根到任意点轻边不超过log n 条

反证法, 如果大于log n 条,

则最深的轻边的根至少还额外连了一个点大小为1的子树

第二深的轻边的根至少还额外连了一个点大小为3的子树

第三深的轻边的根至少还额外连了一个点大小为7的子树

…

第m深的轻边的根至少还额外连了一个点大小为2^m-1的子树

显然 m > log n , 则 2^m - 1 > n - 1 >= n

性质得证

那么每个节点只有在它的某个祖先u的视角, 它是u的轻边的那一部分时, 才会作为被遍历的

所以每个节点的被遍历次数 = 它到根的轻边数

所以 O(n log n)

代码

https://codeforces.com/contest/1709/submission/165472602

#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 pb push_back

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

const int N = 200000;
int ans=0;
int a[N+10]; // read
int p[N+10]; // 当前每个节点对应st节点下标 pos[u]
vector<int> e[N+10]; // edge
set<int> st[N+10]; // st[顶点] = {链到根的xor集合}

void dfs(int u,int f, int x) {
  int &iu = p[u]; // 真的u
  int bu = x^a[u]; // 从根下来的xor 链
  st[iu].insert(bu);
  bool delu = false; // delete u
  for(auto v:e[u]) if(v != f){
    dfs(v,u,bu);
    int &iv = p[v];
    // 把小的向大的合并, 结果存在st[iu] 中
    if(st[iu].size() < st[iv].size()) swap(iu, iv);
    for(auto val:st[iv]){
      if(delu) break;
      if(st[iu].count(val ^ a[u])) delu = true;
    }
    if(!delu) for(auto val:st[iv]) st[iu].insert(val);
    st[iv] = {};
  }
  if(delu){
    st[iu] = {};
    ans++;
  }
}

int main() {
  int n = read();
  rep(i,1,n+1) {
    a[i] = read();
    p[i] = i;
  }
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }
  dfs(1,0,0);
  printf("%d\n",ans);
}

F

题目

https://codeforces.com/contest/1709/problem/F

读入 n, k ,f

包含长度等于n的字符串的可重集合 beautiful 定义为

对于长度 [1,n] 之间任意字符串s, c[s] >= 集合中以s为前缀的字符串个数

任务对于[1,n] 的所有字符串s, 你需要计算有多少中映射c[s] 的选择方式

max(beautiful的集合的元素个数 )= f

其中 0 <= c[s] <= k

范围

n 15

k,f 2e5

6s

512ms

题解

我的思路

显然关于前缀

如果 s0 是 s1的前缀

那么显然 s0 出现的次数 >= s1 出现的次数

那么如果 c[s0] <= c[s1] , c[s1] 就没什么作用

反过来, 如果 c[s0] >= sum c[s0的所有下一级后缀], 那么c[s0] 也不是紧限制

因此真正有效的内容是

c[s1] <= c[s0] ,c[s0] <= sum c[s0的所有下一级后缀],

而这样约束以后, 方案数就 = c[0] + c[1], 因为每个都表示能达到的最大个数

问题来了, 这样如何算原始的c呢

题解

转化一下题目

高度n的满二叉树

你需要对每个父子之间做最大流量限制,[0,k] 之间整数

让根源, 所有叶子汇, 的最大流恰好 = f

求方案数 % 998244353

对于给定k

a(n,f) = 高度n, 最大恰好f的方案数

考虑状态转移

那么也就是左边的n-1高度最大流为v的时候,右边为f-v

但是这个左边的最大流可能是被根到左边这个边限制的, 也可能是本身n-1,v 的方案

定义 b(n,f) 等于高度n 且根上多一个[0,k] 的限制的最大流 = k,方案数

如果是下面子树最大f, 那么对于根上可以选择 f~k, 所以有(k-f+1)a(n,f) 种

如果是下面子树最大 > f, 那么对于根上仅可选择f, 所以有 $\sum_{i=f+1}^{2k} a(n,i) 种

综上$b(n,f) = (k-f+1)a(n,f) + \sum_{i=f+1}^{2k} a(n,i)$ , 前缀和每个状态均摊O(1) 可算

那么对于a就是最开始的转移

$a(n,f) = \sum_{i=0}^f b(n-1,i)\cdot b(n-1,f-i)$, 卷积, 需要FFT或者NTT就可以搞

那么答案 = $a(n,f)$, 也说明 $f > 2k$ 无解

最后边界处理, $b(n,f) = 0, f > k$

关于实现, 似乎直接NTT c++17会被卡, 可能要c++20

因为这里相当于是$a[n] = b[n-1]^2$, 所以平方可以少算一次NTT

然后注意计算前把末尾0删了, 不然可能长度倍增

以及我本地测带了-fsanitize的编译, c++17/20 都4.5s, 而不带的都是1s

代码

https://codeforces.com/contest/1709/submission/165613575

#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;)
#define pb push_back

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

// ------------------------------- NTT --------------------------------
namespace NTT998{
  const int MOD = 998244353; // 7*17*2^23 + 1
  const int MAXPWR = 22; // 随着MOD改变, 2的幂次, 对应复平面单位向量的N = 2 && MAXPWR;
  const int g = 3;// 原根 随着MOD改变
  const int invg = 332748118;// 原根模逆元 随着MOD 和 g 改变

  // bit 翻转
  int rev(int x, int len) {
    int ans = 0;
    while(len -- ){
      ans <<= 1;
      ans |= x & 1;
      x >>= 1;
    }
    return ans;
  }

  inline int getlog2(int n){ return 31 - __builtin_clz(n);}

  ll mypow(ll a, ll k) { //快速幂，a**k
    ll res = 1;
    while (k) {
      if (k & 1) (res *= a) %= MOD;
      (a *= a) %= MOD;
      k >>= 1;
    }
    return res;
  }

  void NTT(vector<ll> &A, int flag = 1 /* 1: NTT, -1: INTT*/ ) {
    int n = A.size();
    if(n == 1) return ;
    // assert((n & (n-1)) == 0); // 2 的幂次
    int lgn = getlog2(n);
    // assert(lgn <= MAXPWR);
    rep(i, 0, n) { // 同FFT
      int j = rev(i, lgn);
      if (j > i) swap(A[i], A[j]);
    }
    rep(pwr,0,lgn){
      int m = 1 << pwr;
      // assert((MOD - 1) % (m<<1) == 0);
      ll gn = mypow(flag == 1 ? g : invg, (MOD - 1) / (m << 1)); // 单位原根g_n
      for (int k = 0; k < n; k += (m<<1)) {
        ll gi = 1;
        rep(j,0,m) {
          auto U = A[k + j];
          auto T = gi * A[k + j + m] % MOD;
          A[k + j] = (U + T) % MOD;
          A[k + j + m] = (U - T + MOD) % MOD;
          (gi *= gn) %= MOD;
        }
      }
    }
    if(flag == -1){ // 内置 / N
      const ll INVSIZE = mypow(n, MOD-2);
      rep(i,0,n) (A[i] *= INVSIZE) %= MOD;
    }
  }

  void INTT(vector<ll> &A){ NTT(A,-1);}

  // 平方 少一次 NTT
  vector<ll> poly_sq(vector<ll> &v0) {
    int sz = v0.size() * 2;
    if(sz == 0)return {};
    sz = 1 << (getlog2(sz) + !!(sz & (sz-1))); // 非2的幂次
    v0.resize(sz,0);
    NTT(v0);
    vector<ll> a2(sz,0);
    rep(i,0,sz) a2[i] = v0[i] * v0[i] % MOD;
    INTT(a2);
    return a2;
  }
}

// ------------------------------- NTT --------------------------------

int n;

vector<ll> a;
vector<ll> b; // 滚动

int main(){
  const int MOD = NTT998::MOD;
  int n = read(); // 15
  int k = read(); // 2e5
  int f = read(); // 2e5
  if(f > 2 * k){
    printf("0\n");
    return 0;
  }
  b = vector<ll>(k+1,1);

  rep(i,1,n+1){
    // a
    a = NTT998::poly_sq(b); // 非平方也会TLE
    if(a.size() <= 2*k+1) a.resize(2*k+1,0);
    vector<ll> prea(2*k+2, 0); // prefix sum of a
    rep(j,0,2*k+1) prea[j+1] = (prea[j] + a[j]) % MOD;

    b = vector<ll>(k+1,0);
    rep(j,0,k+1) b[j] = (k-j+1) * a[j] % MOD + (prea[2*k+1] - prea[j+1]);
    while(!b.empty() && b.back() == 0) b.pop_back(); // 重要, 否则多出来的0 会导致 长度倍增 TLE
  }

  printf("%lld\n", a[f]);
  return 0;
}

总结

E

一个是细节想错, lca多算一次没想到

另一个是考虑最深的lca的根 ,而不是考虑端点

这两点都是能想到没想到

然后关键的来了, 就是启发式合并的知识点, 这下学会了又

F

一个是变成树的 “流计算”, 很神奇我好想竖着觉得是树 ,横着就没发现了,

一个是学一下NTT, 以及NTT中的平方

参考

官方

NTT

相关内容

最终产物

FWHT

解决什么问题

G - Power Pair

题目

范围

题解

我的思路

官方

代码

H/Ex - Nim Counting

范围

题解

我的思路

官方

代码

总结

参考

NTT

解决什么问题

离散傅立叶变换

E

范围

题解

我的思路

题解

启发式合并(DSU on Tree)

代码

F

题目

范围

题解

我的思路

题解

代码

总结

参考