YeXiaoRain Blog

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

發表於 更新於 分類於 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}}.}$

閱讀全文 »

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

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

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

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

Lindström–Gessel–Viennot lemma

https://oi-wiki.org/graph/lgv/

前置知识, 图论基础,矩阵,行列式,高斯消元

适用于DAG上(有向无环图)

定义

$P$ 路径

$\omega(P) = $ 路径$P$上边权之积

点$u,v$

$e(u,v) = \sum_{P:u\to v} \omega(P)$每一条 $u$到 $v$ 的路径$S$,的$\omega(P)$之和

大小为n的 起点集合A,终点集合B, (点集内也可能有边, 满足DAG, 以及还有一些不是起点也不是终点的其它中间的点

$S$ 一组不相交的路径组(路径集合,包含所有起点终点): 任意两个路径$S_i,S_j$没有公共顶点

$\sigma(S)$ 表示一个具体的路径集合$S$中,$A$按照顺序($S_i$的起点是$A_i$)时, $B$的下标序列

$N(\sigma) = \sigma$的逆序对个数

系数矩阵

$M = \begin{bmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n) \\
e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n) \\
\vdots&\vdots&\ddots&\vdots \\
e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n)\end{bmatrix}$

閱讀全文 »

發表於 更新於 分類於 ， Disqus： 文章字數： 4.1k 所需閱讀時間 ≈ 14 分鐘
C(最小生成树,LCA,树上差分)D(组合数,树上DP,DP,前缀和)E(数学,倍增)

C

https://codeforces.com/contest/1707/problem/C

给你个n点,m边的连通图,边两两不等

有个错误的dfs算法, 每次找未选择的点中最短边进行dfs

问,从哪些点开始dfs,能得到正确的最小生成树

范围

n 1e5

m [n-1,2e5]

2s

256MB

题解

我的思路

首先边两两不等,说明正确的最小生成树唯一

第二以一个点作为根, 按正确的最小生成树建树, 那么树边以外的其它边都是回边,没有跨边,则这个点做dfs合法

但这样每次枚举就是 O(n^2), TLE

题解

先找到最小生成树

如果有连接 u v的非树边

那么 通过树边的简单路径 u—–v 通过树边的中间的点, 不可能, 且沿着树边扩展的点也不可能

变成了树上染色问题

然后剩下就LCA,树上差分了

LCA + 树上差分 思想就是

初始是对不可能的+1

然后因为批量+1 复杂度大

变成了记录每个数和它父节点的差(根节点表示自身的值), 就是树上差分了

那么对于 u,v 是非祖先关系, c[根]+=1,c[u]-=1,c[v]-=1

u和v是祖先关系, 假设u是v的祖先

c[u向v的子节点]+=1, c[v]-=1

最后还原差分成真实树即可, 判断 > 0?

代码

https://codeforces.com/contest/1707/submission/164711832

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
#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
const int POWER = 20;
const int N = 100000;
const int M = 200000;

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

int n;
int m;
vector<int>p2[N+10]; // MST
pair<int,int> e[M+10]; // 边
bool treee[M+10]; // tree edge

int f[N+10]; // 并查集
int find(int v) {return f[v]==v?v:(f[v] = find(f[v]));}
void link(int u,int v){ f[find(v)] = find(u);}

ll x[N+10]; // 差分 和最终值
int fa[N+10][POWER]; // 树上倍增
int d[N+10]; // 深度
// 一级父节点 和 深度
void build(int u,int p = 1,int dep = 1){
  fa[u][0] = p;
  d[u] = dep;
  for(auto v:p2[u]) if(v != p) build(v,u,dep+1);
}
// 还原差分
void dfs(int u, int p = 1, int s = 0){
  x[u] += s;
  for(auto v:p2[u]) if(v != p) dfs(v,u,x[u]);
}
// 最近公共祖先
int lca(int u,int v){
  if(d[u] < d[v])swap(u,v); // d[u] > d[v]
  per(i,0,POWER) if(d[u] - d[v] >= (1 << i)) u = fa[u][i];
  if(u == v) return u;
  per(i,0,POWER) {
    if(fa[u][i] != fa[v][i]){
      u = fa[u][i];
      v = fa[v][i];
    }
  }
  return fa[u][0];
}
// u 向上走d步
int fa_d(int u,int d){
  per(i,0,POWER) if(d >= (1 << i)) {
    d -= (1<<i);
    u = fa[u][i];
  }
  return u;
}

int main(){
  // read
  n = read();
  m = read();
  rep(i,0,m){
    int u = read();
    int v = read();
    e[i] = {u,v};
  }
  // MST
  iota(f+1,f+n+1,1);
  rep(i,0,m){
    auto [u,v] = e[i];
    if(find(u) != find(v)) {
      treee[i] = true;
      link(u,v);
      p2[u].pb(v);
      p2[v].pb(u);
    }
  }
  // 建立倍增
  build(1); // 深度 和 1级父节点
  rep(pwr,1,POWER) rep(i,1,n+1) fa[i][pwr] = fa[fa[i][pwr-1]][pwr-1];

  // 树上差分
  rep(i,0,m) if(!treee[i]){
    auto [u,v] = e[i];
    if(d[u] > d[v]) swap(u,v); // d[u] < d[v];
    int r = lca(u,v);
    if(u == r){
      int w = fa_d(v, d[v] - d[u] - 1);
      x[w]++;
      x[v]--;
    } else {
      x[1]++;
      x[u]--;
      x[v]--;
    }
  }
  // 差分还原成值
  dfs(1);
  // 输出答案
  rep(i,1,n+1) printf("%d", (int)(x[i] == 0));
  return 0;
}

D

https://codeforces.com/contest/1707/problem/D

题目

n 点 根为1树

初始 U = 1..n 点集合

一次操作, 取点集T, T 是U的部分虚树(T是U的真子集, 且T中任意两点的LCA也属于T), 令U=T

求 恰好k次操作后 集合只有根节点的操作路径有多少种

方案数 mod p

要求 k=1,2,…,n-1 所有的结果

范围

n 2000

p [1e8+7 ~ 1e9+9] 是 质数

2s

256mb

题解

我的思路

可能可以倒过来

初始只有根,每次增加至少一个点, 增加后要满足LCA的在集合中的关系, 一共k次

考虑一个叶子节点, 它可以任意时候被加入

一个非叶子只有一个分支的节点, 它也是任意时刻被加入

一个非叶子,多分支节点那么它加入的时机 需要 早于或等于 它的第二个被加入的子树

换句话说, 假设点i为多叉点,在t时刻被加入,那么 1..t-1 中至多只能存在点i 的其中一个子树中的点

f(t..k, all子树)

  • f(1..k, 子树1, 至少一个在[1..t-1]) * f(t..k, all子树-子树1) +

  • f(1..k, 子树2, 至少一个在[1..t-1]) * f(t..k, all子树-子树2) +

  • …

但似乎 注意到一个子树放在区间至于区间长度有关, 这样至少后面一半状态上是nk的

前面一节, 可以变成f(1..k,子树1) - f(t..k, 子树1) 这样剩下的至少一个不属于(t..k)

f(根u, 长度l) = for t = 1..l

转移还要n, 这样n^3, 而且还有k, 一眼TLE

考虑到本来状态就是 f(根u, 长度l) 也就是对于不同k可以复用, 那么问题来到了如何把转移优化到 log或者常数级别, 或者均摊常数级别

f(u,l) = f(v0, k - t + 1) * f(v1)

如果干掉这个t就好了

题解

如果每次点数不严格下降结果为f,原答案为ans

有 $f_i=\sum_{j=0}^i\binom{i}{j}ans_j$, 因为j步意味着j+1个不同的集合, 要用这j+1个不同的集合按原顺序,可重复的产生i+1个集合, 那么其实就是选择每个开始的位置

既然是带系数前缀和,那也可以从 f反向推ans, 所以问题怎么球不严格下降的结果

然后又是来到和我讨论类似的对删除时间的讨论

当一个节点u有分叉时

那么它的删除时间就会受到 子树的限制

  1. 子树里所有节点 早于等于 u

  2. u的某个子树以外的子树都删完了 早于等于 u, 早于剩下的子树最后一个节点

状态 dp[u][t] , u以及它的子树,恰好第i次操作后删除完的方案数

转移 $dp_{u,t}$

$C_u$ 是 $u$ 的子节点集合

前缀 $S_{u,t} = \sum_{i\le t} dp_{u,i}$

$u$子集前缀关于$t$的乘积 $M_{u,t} = \prod_{v \in C_u} S_{v,t}$

  1. $u$在$t$时刻删, 则 剩下的都在$[1,t]$时刻删

$M_{u,t}$

  1. $u$在$t_0 < t$ 时刻删, 因为要恰好, 则至少有个在$t$时刻删, 其它在$[1,t_0]$时刻删

$ \sum_{v\in C_u} (dp_{v,t} \cdot \prod_{w \in C_u, w \neq v}^N S_{w,t_0})$

$ = \sum_{v\in C_u} (dp_{v,t} \cdot \frac{\prod_{w\in C_u} S_{w,t_0}}{S_{v,t_0}})$

$ = \sum_{v\in C_u} dp_{v,t} \cdot \frac{M_{u,t_0}}{S_{v,t_0}}$

对于所有$t_0 \in [1..t-1]$ 加和

$ = \sum_{t_0 = 1}^{t-1} (\sum_{v\in C_u} dp_{v,t} \cdot \frac{M_{u,t_0}}{S_{v,t_0}})$

$ = \sum_{v\in C_u} (dp_{v,t} \cdot (\sum_{t_0 = 1}^{t-1} \cdot \frac{M_{u,t_0}}{S_{v,t_0}}))$

综上

$ dp_{u,t} = M_{u,t} + \sum_{v\in C_u} (dp_{v,t} \cdot (\sum_{t_0 = 1}^{t-1} \cdot \frac{M_{u,t_0}}{S_{v,t_0}}))$

每个$S_{u,t}$, 均摊只需要O(1), $S$总状态$O(n^2)$, 所以时间复杂度$O(n^2)$

然后每个$M_{u,t}$ 均摊需要$O(|C_u|)$, 对于所有$u$的$|C_u|$和为 节点数,所以时间复杂度也是$O(n^2)$

再看 $\sum_{t_0 = 1}^{t-1} \cdot \frac{M_{u,t_0}}{S_{v,t_0}}$

注意和$u,v,t$ 有关,但v只能是u的子节点集, 所以状态数为$O(|C_u|n)$, 总状态数依然是$O(n^2)$, 同样通过t的前缀和, 均摊$O(1)$, 所以总时间复杂度也是$O(n^2k)$

最后$dp_{u,t}$, 状态显然$O(n^2)$, 时间复杂度$O(|C_u|)$, 所以总时间复杂度$O(n^2)$;

可做……….

咦,看起来和我的很像啊, 是不是我的那个t也可以干掉

可能不一定,别人通过恰好来简化了转移方便了前缀和实现

最后的最后, 通过$ans_i = f_i - \sum_{j=0}^{i-1} \binom{i}{j} ans_j $反推即可

实际写起来有几点坑,

  1. 时间卡得紧, 不要频繁的用费马小定理 计算inv, TLE11

  2. Wa31 第31个点 会出现S是MOD的倍数…..

然后Wa31需要小学数学, 因为本身是乘法, 变成除法只是为了简化运算, 所以本身不会有除0, 但 变化后 加上mod 就可能除以0

注意到这里其实就是M和S之间,所以统计一下M中少乘一个零的结果, 当S=0时取那个结果即可

然后 因为量级很大, 不能去 大量做mod除法, 所以一个办法是记录 分子分母, 另一个办法是

M/S也变成前缀+后缀的形式来算, 当然前缀+后缀形式会常数更小

代码

分数+除法 857ms 158MB

https://codeforces.com/contest/1707/submission/164894672

前后缀 + longlong 733ms 81MB

https://codeforces.com/contest/1707/submission/164900140

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

int MOD = -1;

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll mpow(ll v,ll mi){ll r = 1;while(mi){if(mi%2)(r*=v)%=MOD;(v*=v)%=MOD;mi>>=1;};return r;} // quick power with MOD

int n;

vector<int> e[2010];

void dfs(int u,int fa){
  vector<int> arr = {};
  for(auto v: e[u]) if(v != fa) arr.pb(v);
  e[u] = arr;
  for(auto v: e[u]) dfs(v, u);
}

struct ModInt{
  int v;
  ModInt(ll val = 0) :v(val) { }
};

ll real(const ModInt & v0){
  return (v0.v + MOD) % MOD;
}

ModInt operator+(const ModInt & v0, const ModInt &v1){
  return (v0.v + v1.v) % MOD;
}

ModInt operator-(const ModInt & v0, const ModInt &v1){
  return (v0.v - v1.v) % MOD;
}

ModInt operator*(const ModInt & v0, const ModInt &v1){
  return ((ll)v0.v * (ll)v1.v) % MOD;
}

ModInt dp[2010][2010];
vector<ModInt> preMu[2010]; // 每次只会具体 u 可以复用
vector<ModInt> sufMu[2010];
ModInt S[2010][2010];
ModInt W[2010][2010];

ModInt fac[2010] = {1};
ModInt invv[2010] = {1};
ModInt invfac[2010] = {1};
ModInt C(int n,int m) { return fac[n] * invfac[m] * invfac[n-m]; }

ModInt ans[2010];

int main(){
  n = read();
  MOD = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }

  // 30 ms
  rep(i,1,n+1) fac[i] = fac[i-1] * i;
  invv[1] = 1;
  rep(i,2,n+1) invv[i] = (MOD-MOD/i) * invv[MOD % i];
  rep(i,1,n+1) invfac[i] = invfac[i-1] * invv[i];

  dfs(1, 1);
  // 61ms
  // bfs on tree
  vector<int> vorder = {1};
  rep(i, 0, vorder.size()) {
    int u = vorder[i];
    for(auto v: e[u]) vorder.pb(v);
  }
  reverse(vorder.begin(), vorder.end());

  for(auto u: vorder) {
    rep(t,1,n) {
      ModInt &dput = dp[u][t] = 1; // 叶子
      if(!e[u].empty()) {
        // 优化成 前后缀
        preMu[t] = vector<ModInt> (e[u].size() + 1, 1);
        sufMu[t] = vector<ModInt> (e[u].size() + 1, 1);
        rep(i,0,e[u].size()){
          auto v = e[u][i];
          preMu[t][i+1] = preMu[t][i] * S[v][t];
        }
        per(i,0,e[u].size()){
          auto v = e[u][i];
          sufMu[t][i] = sufMu[t][i+1] * S[v][t];
        }
        dput = preMu[t][e[u].size()];
        if(t > 1) rep(i,0,e[u].size()) {
          auto v = e[u][i];
          ModInt &Wvt = W[v][t-1] = ((t-1 > 1) ? W[v][t-2] : 0) + (preMu[t-1][i] * sufMu[t-1][i+1]);
          dput = dput + dp[v][t] * Wvt;
        }
      }
      S[u][t] = ((t > 1) ? S[u][t-1] : 0) + dput;
    }
  }

  rep(t,1,n) ans[t] = preMu[t][e[1].size()];
  rep(t,1,n) rep(t0,1,t) ans[t] = ans[t] - ans[t0] * C(t,t0) ;
  rep(t,1,n) printf("%lld ", real(ans[t]));
  return 0;
}

E

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

题目

长度n数组 a

$ai \in [1,n]$

f((l,r)) = (min(a[l..r]) , max(a[l..r])), 传入区间范围, 返回最小值和最大值

每次调用 (l,r) = f((l,r))

q个询问

每次问如果初始 li,ri, 需要反复调用 多少次 让l和r 最终变成(1,n) 或不可能

范围

q 1e5

n 1e5

题解

我的思路

显然对于给定l,r 输出的f是一定的

所以对于所有的输入, 全部成环

那么f( (1,n) ) 一定要等于 (1,n), 否则 只有直接传入1,n 才会满足

想倒着找, 但是显然有最坏情况, 2 3 4 5 6, 这样一共有$O(n^2)$种不同输入和结果

题解

如果 区间A 包含于区间B

那么 f(A) 包含于 f(B)

证明, min(B) <= min(A) <= max(A) <= max(B)

并且高阶f也有这个包含关系

因此如果 [l,r] = ([l,r0] 并 [l0,r]), 其中 (l0 <= r0)

那么 f(l,r) 包含 (f(l,r0) 并 f(l0,r)),

注意到 f(l,r0) 包含 f(l0,r0), f(l0,r) 也包含 f(l0,r0)

所以 f(l,r0) 和 f(l0,r) 本身就重叠, 所以 f(l,r0) 并 f(l0,r) = 连续的区间

那么 f(l,r) 的最小值 至少包含于 f(l,r0) 和 f(l0,r) 的其中一个, 最大值也是, 所以最小值最大值都存在,且连续, 包含于 f(l,r)

综上 f(l,r0) 并 f(l0,r) = f(l,r)

同样高阶也满足

例如2阶段, f(f(l,r)) = f(f(l,r0)) 并 f(f(l0,r)) , 思路同上, 包含于关系, 最小 最大值, 连续 推出相等

注意到 一旦能到整个长度,那么一定 f(1,n) = (1,n)

如果链很长, 根据状态数 可能达到n^2

那么 办法就是倍增, 倍增到> n^2 如果还不行那就真不行了

可以的话就二分倍增的倍数

为了效率, 用倍增记录每个位置开始的长度的 多少轮跳跃的结果

然后实现上几点注意, 别二分, 每次二分会导致 长度不是幂次 依然需要log, 多层log过不了

找结果依然是倍增的找

然后就是cpu缓存和tlb机制, 注意循环顺序访问顺序和数组定义顺序

这导致常数影响非常明显, tle的代码和600+ms过的代码 就是把顺序换了换

然后我看有人 长度开的2^18 也过了!!!, 不知道数学上是否有办法证明或者找反例

代码

https://codeforces.com/contest/1707/submission/164951002

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
#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
 
const int N = 100000;
const int PLEN = 19; // power length math.log(100000) / math.log(2) 16.609640474436812
const int POP = 35; // power operation math.log(4999950000) / math.log(2) 32.219266521851075
 
ll n;
 
int L[POP][PLEN][N+10]; // 次数不用记录零次
int R[POP][PLEN][N+10];
 
int LG2[N+10]; // 0 和 1 都对应0次方, 需要减的 1<<LG2[r-l]的偏移量
 
int a[N+10];
 
inline pii f(int l,int r,int p1){
  if(l == r) return {
    L[p1][0][l],
    R[p1][0][r]
  };
  int sz = LG2[r-l];
 
  return {
    min(L[p1][sz+1][l],L[p1][sz+1][r-(1<<sz)]),
    max(R[p1][sz+1][l],R[p1][sz+1][r-(1<<sz)])
  };
}
 
inline int query(int l,int r){
  if(l == 1 && r == n) return 0;
  if(l == r) return -1;
  // 不要二分, 二分是 log(n^2) = 2 log(n) * log(n)
  // 直接binary 倍增做, log(r-l+1)*O(1) < log(n)
  ll ret = 0;
  per(i, 0, POP){
    // printf("%d = %d\n",r-l,p0);
    int l0, r0;
    tie(l0, r0) = f(l, r, i);
    if(l0 != 1 || r0 != n){
      // checklrk(l, r, 1ll << i, l0, r0);
      l = l0;
      r = r0;
      ret += (1ll << i);
      if(l == r) return -1;
    }
  }
  tie(l,r) = f(l, r, 0);
  return (l == 1 && r == n) ? (ret + 1) : -1;
}
 
int main(){
  n = read();
  rep(i,2,N) LG2[i] = LG2[i/2] + 1;
  int q = read();
  rep(i,1,n+1) L[0][0][i] = R[0][0][i] = a[i] = read();
  {
    const int p1 = 0;
    rep(p0,1,PLEN) rep(i,1,n+1) {
      L[p1][p0][i] = min(L[p1][p0-1][i],L[p1][p0-1][min(n,i+(1ll << max(0ll, p0-2)))]);
      R[p1][p0][i] = max(R[p1][p0-1][i],R[p1][p0-1][min(n,i+(1ll << max(0ll, p0-2)))]);
      // check(i,p0,p1);
    }
  }
  rep(p1, 1, POP) rep(p0, 0, PLEN) rep(i,1,n+1){
    tie(
        L[p1][p0][i] ,
        R[p1][p0][i]
       ) = f(
         L[p1 - 1][p0][i],
         R[p1 - 1][p0][i],
         p1 - 1
         );
  }
 
  while(q--){
    int l = read();
    int r = read();
    printf("%d\n", query(l,r));
  }
  return 0;
}

总结

C

有想到, 环的最大边的 两点以外的点不可能,但是有反例, 就是没有把最小生成树 和 这个合在一起考虑

后面LCA和树上差分倒是没啥问题掌握了

D

感觉真有可能能做出来, 多习惯在dp时 分别恰好,和 小于等于 ,以及 前缀和方程与逆方程之间的联系

被小学数学教育了$a \neq \frac{a\cdot b}{b}$

然后就是 大量的inv还是不要, 一个办法就是 分数表示, 一个办法是想办法消除掉除法

E

数学推出性质以后 就是倍增倍增倍增了

实现上也有一些坑

参考

官方

0%