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

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

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

实现上也有一些坑

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
D(数学,组合数),E(有向图,并查集,gcd,所有环,树回边)

D

题目

https://atcoder.jp/contests/arc144/tasks/arc144_d

有多少个映射f满足

定义域[0..2^n-1]

值域[0..k]

且值域内任意值x,y满足

f(x) + f(y) = f(x & y) + f(x | y)

范围

n 3e5

k 1e18

2s

1024mb

题解

我的思路

f(…0) + f(1) = f(…1) + f(0)

f(…0.) + f(10) = f(…1.) + f(0)

因此 自由元素 f(0) f(1) f(2) f(4) …

把 f(0..2^{n-1}-1)看作整体, 那么 f(2^{n-1}..2^{n}-1) 可以看作它的平移

显然有

dp[i][min][max] = sum{dp[i-1][min][min..max]} + sum{dp[i-1][min..max][max]} - dp[i-1][min][max]

然而这 $O(nk^2)$ 显然时间空间都接受不了

不知道怎么化简

题解

跟着上面思路 如果 f(0) = 0 , 那么 f(x) = 按二进制拆开x的 sum f(bit)

相当于 f(1) + f(2) + f(4) + f(8) … <= k 插板组合数

如果f(0) != 0, 令 f(0) = V

那么令 g(x) = f(x) - V

那么g(x) 也满足条件, -V <= g(x) <= K - V

0 <= sum g(任意2幂) + V <= k

sum 正g(2幂) + V <= k

sum 负g(2幂) + V >= 0

然后就是

枚举f(0) 的值V

枚举正数个数i, i个正的和 $\le k-V$, 因为小于等于 所以不妨把k-V-和+1 看作一个新的正数,相当于 i+1个正数 和 = k-V+1, 那就是k-V空隙插i个板子

枚举负数个数j,同理

$\sum_{V=0}^k \sum_{i=0}^n \sum_{j=0}^{n-i} \binom{n}{i} \binom{n-i}{j} \binom{k-V}{i} \binom{V}{j}$

$\sum_{i=0}^n \sum_{j=0}^{n-i} \binom{n}{i} \binom{n-i}{j} (\sum_{V=0}^k \binom{k-V}{i} \binom{V}{j})$

$\sum_{i=0}^n \sum_{j=0}^{n-i} \binom{n}{i} \binom{n-i}{j} (\sum_{V=j}^{k-i} \binom{k-V}{i} \binom{V}{j})$

右侧括号里,可以想成$k+1$个球, 选出$i+j+1$个球的组合方案数

我们去枚举被选的第$i+1$个球的位置$p$, $p \in [i+1,k+1-j]$

那么左侧有$p-1$个, 需要选出$i$个, 右侧有$k + 1 - p$个需要选出$j$个

令$V = k + 1 - p$即和现在表达式一致了

所以

$\sum_{i=0}^n \sum_{j=0}^{n-i} \binom{n}{i} \binom{n-i}{j} \binom{k+1}{i+j+1}$

$\sum_{i=0}^n \sum_{j=0}^{n-i} \binom{i+j}{i} \binom{n}{i+j} \binom{k+1}{i+j+1}$

$\sum_{i+j \le n} \binom{i+j}{i} \binom{n}{i+j} \binom{k+1}{i+j+1}$

二项式和

$\sum_{s = 0}^n 2^s \binom{n}{s} \binom{k+1}{s+1}$

就可以做了

代码

https://atcoder.jp/contests/arc144/submissions/33279666

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

ll mul(ll a,ll b){
  a %= MOD;
  b %= MOD;
  return a * b % MOD;
}

ll add(ll a,ll b){
  a %= MOD;
  b %= MOD;
  return (a + b) % MOD;
}

ll normal(ll a){
  return (a%MOD + MOD)%MOD;
}

ll mypow(ll v,ll pwr){
  v%=MOD;
  ll r = 1;
  while(pwr){
    if(pwr%2) (r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}

ll fac[300010] = {1};

ll binom(ll n,ll m){
  if(m > n) return 0;
  return fac[n] * mypow(fac[m],MOD-2) % MOD * mypow(fac[n-m],MOD-2) % MOD;
}

int main(){
  rep(i,1,300005) fac[i] = mul(fac[i-1],i);
  int n = read();
  ll k = read();
  ll ans = 0;
  ll binomk1s1 = 1; // k 很大
  rep(s,0,n+1){
    if(s > k) break;
    binomk1s1 = mul(binomk1s1,mul(k+1-s,mypow(s+1,MOD-2)));
    ans = add(ans,mul(mul(mypow(2,s),binom(n,s)),binomk1s1) );
  }

  printf("%lld\n", normal(ans));
  return 0;
}

E

题目

N点,M边有向图

有向边 都是从小节点指向大节点的(无自环,无重边)

输入一个初始W[1..N],其中如果是Wi=-1,就可以取任何值,否则按给定的来

点i 权重 Wi

求最大从1到N的所有路径的权重和的gcd

如果gcd可能无限大则输出-1

不需要输出W的方案

范围

N 3e5

M 3e5

至少存在一条路径

初始Wi [1…10e12]

2s

1024MB

题解

我的思路

首先 如果存在一条完全给定的 1->N的权重和则有限大,否则可能无限大(A->B, B->C->D, B->D, 其中B任意,而后面指定两条路径不等, 那么gcd也是有限大)

对于有限大, 因为有向边全是从小指向大, 所以不成环只有拓扑关系

在没有具体值的情况, 并不能对求和的表达式计算gcd

所以考虑有没有可能反过来

反过来指定gcd, 1个问题是并没有二分性质, 每条边的可能性是考虑mod gcd,也是gcd个, 量级也不会太小

对于直接有指定W路径的相对好一些, 其中gcd一定是它的约数,这样情况会少一些,但是Ai和M都很大,即使给定的路径W和也可以达到3e17

题解

首先干掉 1不能到达, 和 不能到达N的点(无效的点), 防止无效的点影响找环的结果

如果k是答案,那么也就是所有路径 和 %k == 0

那么假设 到点u, (1 -> u)%k = p[u] 是唯一的

那么所有直接相邻的 vi->u, 有 p[vi] + w[u] = p[u] (mod k)

说明p[vi] 全部一样

这样, 就并查集了!

然后p[n] = 0, 所以可以加0号点 W[0] = 0, 路径0->1

有直接相邻u->v,且w[v]给定,

说明 两个并查集里的 的union[u] + 3 = union[v]

变成了 一些点, 和一些有权有向边

找所有环, 求gcd, 并不能找所有环,但是gcd性质上, 所有环gcd = 所有(树+回边) gcd

所以就可以搞了

环即可能由0产生, 也会有形如A->B->C->D, A->D, 这样产生

无环 就任意都可以, -1

然后有向图找环 我真不会写

学了一下apiad巨佬的代码, 发现是所有边建立正向和负向, 保证任何简单复杂路径 = 端点简单路径和即 全部像是无向图的有向图, 这样任何一个点可以作为根

代码

https://atcoder.jp/contests/arc144/submissions/33329393

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

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

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll gcd(ll a,ll b){return b == 0?a:gcd(b,a%b);}

const int N = 300000;

int n,m;

vector<int> u2v[N+10]; // 正向边
vector<int> v2u[N+10]; // 反向边

ll w[N+10];
int invalid[N+10]; // 1 无效, 0 有效, -1 未访问
int fa[N+10]; // 并查集

// 并查集
int getfa(int v){ return v == fa[v]?v:(fa[v] = getfa(fa[v]));}
void link(int u,int v){ fa[getfa(u)] = getfa(v);}
// 计算不可达
bool dfs1n(int u){
  int &r = invalid[u];
  if(r != -1) return r;
  if(u == n) return r = 0;
  r = 1;
  for(auto v:u2v[u]) if(!dfs1n(v)) r = 0;
  return r;
}

// 移除不合法
vector<int> rminvalid(const vector<int> &arr){
  vector<int> ret = {};
  for(auto u: arr) if(!invalid[u]) ret.pb(u);
  return ret;
}

vector<pair<int,ll> > p2[N+10];
int vis[N+10];
ll dis[N+10]; // 和根的距离, root distance

void dfs(int idx,ll d,ll & ans) {
  if(vis[idx]) {
    // (环长 = 多树边 + 1回边), (重边), 多回边的环 gcd = 拆分的多个单回边环的gcd的gcd
    ans = gcd(ans, abs(d - dis[idx]) );
    return ;
  }
  vis[idx] = true;
  dis[idx] = d;
  for(auto [v,s]:p2[idx]) dfs(v, d + s, ans);
}

int main(){
  n = read();
  m = read();
  iota(fa,fa+n+1,0); // fa[i] = i
  fill(invalid+1,invalid+n+1,-1); // invalid[i] = -1
  rep(i,1,m+1) { // u -> v
    int u = read();
    int v = read();
    u2v[u].push_back(v);
    v2u[v].push_back(u);
  }
  rep(i,1,n+1) w[i] = read();
  // 筛无效点
  dfs1n(1);
  rep(u,1,n+1) if(!invalid[u]) u2v[u] = rminvalid(u2v[u]);
  rep(v,1,n+1) if(!invalid[v]) v2u[v] = rminvalid(v2u[v]);
  // n -> 1
  u2v[n].pb(1);
  v2u[1].pb(n);

  // 找所有点的源点, 计算并查集
  rep(v,1,n+1) if(!invalid[v]) rep(i,1,v2u[v].size()) link(v2u[v][i-1], v2u[v][i]);
  // 根据给定w 建立新的图
  rep(v,1,n+1) if(!invalid[v] && w[v] != -1){
    int tov = getfa(v); // 并查集中的点
    int fromv = getfa(v2u[v][0]); // assert(v2u[tov].size()); 因为都可达所以每个点一定有前置点
    // 全部双向边 辅助在有向图中找所有环的gcd
    p2[fromv].pb({tov, w[v]}); // 正向
    p2[tov].pb({fromv, -w[v]}); // 负向
  }
  // 找环
  ll ans = 0;
  rep(i,1,n+1) if(!invalid[i] && !vis[i]) dfs(i,0,ans);
  printf("%lld\n",ans == 0? -1: abs(ans));
  return 0;
}


总结

D

这个对f(0) = 0特殊讨论 ,在 讨论f(0) 不为零的转化, 就是 一个特殊边界讨论 + 向特殊转移的问题

然后什么神奇的范德蒙恒等式(这里并不是, 但有一点思路相近的感觉

$\binom{n+m}{k} = \sum_{i=0}^k \binom{m}{i} \binom{n}{k-i}$

其实就是考虑$(1+x)^{m+n}$的$x^k$系数和 $(1+x)^m\cdot (1+x)^n$的$x^k$的系数

总之还有一些组合数的技巧,不是光有了初始表达式就可以的

E

讨论满足目标条件的 相邻转移

然后这个有向找所有环的gcd 也是学了一手, 改成正负双向

参考

官方题解

https://www.bilibili.com/video/BV1aB4y1a74j

發表於 更新於 分類於 Disqus： 文章字數： 370 所需閱讀時間 ≈ 1 分鐘
NTT, 牛顿法求逆多项式

Newton’s method on polynomials

希望找到$F(x)$,使得$A(F(x))=0$

  • 已知 $F_d(x) \equiv F(x) \mod (x^d)$
  • 已知 $[x^0] F(x)$, 即$F_1(x)\equiv [x^0]F(x) \pmod{x^1}$

$A(F(x)) = A(F(x)-F_d(x)+F_d(x))$

$= A(F_d(x)) + A’(F_d(x))(F(x)-F_d(x)) + O((F(x)-F_d(x))^2)$

相当于$F(x)$在点 $F_d(x)$展开，（总觉得有点小怪，这里相当于认为所有的都是 能表示成 幂级数（生成函数）的表达？）

那么两边同时 $\mod x^{2d}$

$A(F(x)) \equiv A(F_d(x)) + A’(F_d(x))(F(x)-F_d(x)) \pmod{x^{2d}}$

因此我们可以从 $F_d(x)$推出 $F_{2d}(x)$

$0\equiv A(F_{2d}(x)) \equiv A(F_d(x)) + A’(F_d(x))(F_{2d}(x)-F_d(x)) \pmod{x^{2d}}$

$F_{2d}(x)\equiv F_d(x) - \frac{A(F_d(x))}{A’(F_{d}(x))} \pmod{x^{2d}}$

用处

  • The Inverse of Formal Power Series
  • 计算 在 给定 $\mod x^t$ 下的 $\frac{1}{f(x)}$

那么 利用上面的

我们想求 $\frac{1}{f(x)}$

那么令 $F(x)=\frac{1}{f(x)}$

对应上面的就是 $A(F(x))=F(x)\cdot f(x)-1 = 0$

带入上面的结论

$F_{2d}(x)=F_d(x)-\frac{F_d(x)f(x)-1}{f(x)}$

???? 对求逆似乎没有帮助, 感觉题解这里似乎哪里不对？

问题在于 令$A$, 重新定义一下$A$

$A(F(x)) = \frac{1}{F(x)}-f(x)$

即 $\displaystyle F_{2d}(x) \equiv F_{d}(x) - \frac{\frac{1}{F_{d}(x)}-f(x)}{-\frac{1}{F_d(x)^2}} \pmod{x^{2d}}$

$F_{2d}(x)\equiv 2F_{d}(x) - F_d(x)^2f(x) \pmod{x^{2d}}$

相关

https://atcoder.jp/contests/abc260/editorial/4469

abc 260 ex

abc 345 ex

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(网络流)H/Ex(分块,讨论)

https://atcoder.jp/contests/abc259/tasks/

G - Grid Card Game

题目

HxW的数阵

选择任意的一些行和一些列, 让被选到的所有格子的和最大(同时被行和列选只统计一次)

且 限制条件,如果格子上的值为负那么 不能同时选它的行和列

范围

H,W [1,100]

Aij [-1e9,+1e9]

2s

1024mb

题解

我的思路

显然 纯非负的行和列一定被选,

所以可以预处理让剩下的所有行列至少包含一个负数

然后考虑说纯选行或选列

但是显然有反例

1
2
3
  1     -1    100
 -1      1 -10000
100 -10000      1

这种情况 最优的是选1行和1列

然后另一个性质是, 显然 和为非正的行和列不会被选, 因为 如果即选了行又选了列,重叠部分非负 两个都选的和是 小于 两个分别的和的

然后没思路了

题解

首先我们令 结果 = 全部正值 都被选了, 考虑变化对结果的影响

  1. 如果一个正的没有被选, 那么它的行列没有直接被选, -Aij
  2. 如果一个负值被选了, 那么它的行和列有一个被选, Aij

如果 Aij < 0 被选了,

  • 如果是行被选, 那么 影响的是 加上 i行的所有负数

  • 如果是列被选, 那么 影响的是 加上 j列的所有负数

于是改变题目

初始分 = 正数和

那么如果 选了i行, 则 损失 i行的所有负值的和

那么如果 选了j列, 则 损失 j列的所有负值的和

对于正的单元没被选的 损失上面值的代价

对于负的单元, 不恩那个同时选行和列

答案 = 正数和 减去 下面网络流的最小割

点:

R[1..H]

C[1..W]

源S,汇T

边:

S->R[i], 容量 行i的所有负值和的绝对值

C[j]->T, 容量 行j的所有负值和的绝对值

R[i] -> C[j] 如果是 Aij > 0, 则 权重 Aij

C[j] -> R[i] 如果是 Aij < 0, 则 权重 无限大

这样考虑

对于 Aij > 0

S->R[i]->C[j]->T 在最小割中, 至少有一条边被割(说至少是因为, 可能 R和T一个集合,S和C一个集合)

对 Aij < 0

也就是最小割一定不会同时割S->R[i],和C[j]->T, 因为如果这样割了

意味着, S,C[j] 是一个集合,R[i],T是一个集合, 就有 C[j] -> R[i] 的无限大, 就不会是最小割了

对于Aij < 0 一定是 S->R[i] 或 C[j]->T, 表示

也就是对于Aij < 0, 至多一个成为割边

然后最小割 = 最大流 Dinic, 或者直接调用官方的maxflow

代码

https://atcoder.jp/contests/abc259/submissions/33171094

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
#include <bits/stdc++.h>
#include <atcoder/maxflow>
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

int n;
int m;
const int N = 100;

const ll inf = 0x3f3f3f3f3f3f3f3f;
int h, w; // 输入
ll a[N+10][N+10]; // 输入
ll rsum[N+10], csum[N+10]; // 行列负数绝对值和

int main() {
  h = read();
  w = read();
  rep(i,1,h+1){
    rep(j,1,w+1) a[i][j] = read();
  }
  atcoder::mf_graph<ll> g(h+w+2); // 传入点数
  int S = 0; // 源
  int T = h+w+1; // 汇
  ll ans = 0;
  rep(i,1,h+1){
    rep(j,1,w+1){
      if(a[i][j] >= 0){
        ans += a[i][j];
        g.add_edge(i, h+j, a[i][j]); // R[i] -> C[j], a[i][j]
      } else {
        g.add_edge(h+j, i, inf); // C[j] -> R[i], inf
        rsum[i] += -a[i][j];
        csum[j] += -a[i][j];
      }
    }
  }
  rep(i,1,h+1) g.add_edge(S, i, rsum[i]); // S -> R[i], 行负数和的绝对值
  rep(j,1,w+1) g.add_edge(h+j, T, csum[j]); // C[j] -> T, 列负数和的绝对值
  printf("%lld\n", ans - g.flow(S, T));
  return 0;
}

H/Ex - Yet Another Path Counting

NxN的矩阵

每次向右或向下走

问有多少种路径,头和尾所在位置的数字相同

范围

n 400

aij [1,N^2]

2s

1024 MB

题解

我的思路

最朴素就是 对不同值分开处理,直接变成 每个值=> 所有位置

然后 (i0,j0) => (i1,j1) 就是组合数

问题是, 如果一个一算,是(N^4)的样子会TLE

考虑是否有办法把结果变成统计合并

题解

分块

更朴素的纯色+dp是, O(n^2)的

所以对于每个颜色根据个数来做不同处理

如果当前颜色点个数 <= n

显然用我的思路里两两去算, 复杂度不超过O(个数^2),这一类的总复杂度小于O(sum{个数^2}) <= O(sum{n * 个数})<= O(n * sum{个数}) <= O(n^3)

如果当前颜色个数 > n , 那就直接dp,也不超过O(n^2), 而这种最多n种颜色最多O(n^3)

综上

都在n^3内

代码

https://atcoder.jp/contests/abc259/submissions/35946797

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint=atcoder::modint998244353;
using namespace std;
#define rep(i,a,n) for(int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
int a[410][410];
vector<pair<int,int>>b[160010];//value->{i,j}
mint c[410][410];
int main() {
  int n=read();
  rep(i,0,n)rep(j,0,n)b[a[i][j]=read()].push_back({i,j});
  rep(i,0,n)c[0][i]=c[i][0]=1;
  rep(i,1,n)rep(j,1,n)c[i][j]=c[i-1][j]+c[i][j-1];
  mint s=0;
  rep(k,1,n*n+1){//kolour
    if((int)size(b[k])<=n){//点少枚举点对
      for(auto[x0,y0]:b[k])for(auto[x1,y1]:b[k])if(x0<=x1&&y0<=y1)s+=c[x1-x0][y1-y0];
    } else{//点多二维dp
      auto t=vector(n,vector<mint>(n,0));
      rep(i,0,n)rep(j,0,n){
        t[i][j]=(i?t[i-1][j]:0)+(j?t[i][j-1]:0)+(a[i][j]==k);
        if(a[i][j]==k)s+=t[i][j];
      }
    }
  }
  printf("%d\n",s.val());
  return 0;
}

总结

G

感觉 完全对网络流类型不熟,即使看了答案也仅是证明, 感觉没有系统的练习相关的建图, 还是不知道从何而起

这里相当于网络流求的是尽可能删除得小的, 利用了 最小割 = 最大流 , 这也是一个点,要求最小值的时候可以考虑让图能含义到最小割

然后就是atcoder内置的maxflow真香啊

Ex

有一说一感觉比G简单

这个分类的第一个复杂度上限推导还是很有意思,有点像之前树上左右部分平方的dp总复杂度是n3不是n4的感觉

参考

官方题解

https://www.bilibili.com/video/BV1KW4y1S7NA

0%