Atcoder abc318

發表於 更新於 分類於 ， Disqus： 文章字數： 1.8k 所需閱讀時間 ≈ 6 分鐘
G(图,网络流)Ex(分治卷积)

https://atcoder.jp/contests/abc318

G - Typical Path Problem

n点,m边无向图

给定3点a,b,c，问是否存在从a到c经过b的简单路径

n 2e5

m 2e5

2s

1024mb

我的思路

找可以切割图的关键路径

按照关键路径切割图，合并

新图是树且树上所有边是原图的关键路径，在新树上找a到c简单路径

那么 就变成a-端点[关键路径]端点-...-端点[关键路径]端点-c

那么就是判断b 是否为其中的端点

或者相邻端点不同时，b属于对应连通块

然而ACx77,WAx16

题解

啊啊啊啊啊啊啊啊，我傻逼了不应该割边，而是割点

因为

1
2
3
4
5
1-2-3-1
1-4-5-1
1-6-7-1

不应该简单合并

所以有和我思路类似的圆方树（Round-square tree）

官方:

题意 = 问是否有两条路径 b..a,b…c 唯一共享点是b

考虑 构建 有向图G’

因为每个点只能使用一次所以把点拆成入点xi和出点yi，通过限制出入的容量为1来保证每个点至多被用一次

1
2
3
4
     x1    y1
s    x2    y2    t
     ...   ...
     xn    yn

连边 for i =1..n, $x_i\to y_i$, 其中$i=b$时容量为2,其它全为1

连边 for i =1..m, $y_{u_i}\to x_{v_i},y_{v_i}\to x_{u_i}$ 表示边

$s\to x_b$容量2, 表示开始，开始虽然没有额外入点，但是通过$x_b\to y_b$实现了b使用2次

$y_a\to t,y_c\to t$

如果有方案那么 最大流=2

边虽然拆成两个，但是如果同时使用了实际上会是$x_{u_i}\to y_{u_i}\to x_{v_i},x_{v_i}\to y_{v_i}\to x_{u_i}$ 是不可能的

而如果有方案，对应的流的表示就是 对应点的 xiyi交替

所以有效方案能被表示，能表示的都是有效的方案，所以网络流最大流=2 和 原问题有方案等价

代码

https://atcoder.jp/contests/abc318/submissions/49633317

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

int main(void){
  int n=read();
  int m=read();
  atcoder::mf_graph<int> g(2*n+2);
  int a=read();
  int b=read();
  int c=read();
  int S=0;
  int T=2*n+1;
  auto f{[](int v){return v*2-1;}}; // 点入口
  auto t{[](int v){return v*2;}};// 点出口
  g.add_edge(S, t(b), 2);
  g.add_edge(t(a), T, 1);
  g.add_edge(t(c), T, 1);
  rep(i,1,n+1) g.add_edge(f(i),t(i),1);
  rep(i,0,m) {
    int u=read();
    int v=read();
    g.add_edge(t(u), f(v), 1);
    g.add_edge(t(v), f(u), 1);
  }
  printf("%s\n",(g.flow(S,T,2)==2)?"Yes":"No");
  return 0;
}

Ex - Count Strong Test Cases

给定两个长度n的排列p,q

构建一个n点n边的图

1
2
for i=1..n:
	建立边(i,pi),边权=Qi

然后需要 删除一些边，让图是没有环的，且被删除的边的权重和尽量小

Alice的方案:

1
2
for i=1..n:
	如果 (i,pi) 在环上，则删除边(i,pi)

Bob的方案:

1
2
for i=n..1:
	如果 (i,pi) 在环上，则删除边(i,pi)

显然答案都是不对的

问题是 所有$(n!)^2$方案中,有多少种p和q,能让他们都输出错误答案?, mod 998244353

n 2e5

3s

1024mb

我的思路

先说正确的吧

首先n点，看成i出,pi进，那么每个点一个出边，每个点一个入边，就是经典的由若干个纯环构成

那么正确答案显然 = 每个环上的最小值的和

而 如果它们找到的有一个不是最小值，那么 一定和也不是答案，因为 它们每个值 对应一个环 对应一个环上最小值，所以它们找的所有值都大于等于对应环上最小值，所以一旦有一个值不一样，那么结果 就是大于正确答案的

所以问题变成 有多少p,q排列方案

构成的图满足

至少一个环的最小值idx不是环上最小的 且 至少一个环的最小值idx不是环上最大的

似乎反过来想更简单

容斥一下

= 所有方案 - alice正确 - bob正确 + alicebob同时正确

所有方案：$(n!)^2$

alice正确：所有环上最小值，也是环上index最小

bob正确：所有环上最小值，也是环上index最大

alice正确+bob正确：所有环都是长度=1，p只有一个方案，q都行，所以是n!

所有环上最小值，也是环上index最小？？？怎么算

环之间的值不影响 环内的大小性质

所以要考虑 对于一个k个点的环，排列在1~k 的方案数, 那么最小值和index同时取1（最小）就行

$((k-1)!)^2$, 一个是控制p,表示连接的顺序，一个是控制Q表示按照顺序的q的赋值

那么 总的方案 - 包含i=最小的方案变成子问题

1
2
3
4
5
6
7
8
9
f(0) = 1
f(sz) = 
	res = 0
	for s = 1..sz: // 包含 最小i 的环的大小是s
		res += 
			binom(sz-1,s-1) * // 选 除了最小 的i
			binom(sz,s) * // 选Q
			((s-1)!)^2 *  // 环内排序
			f(sz-s) // 剩余部分

$\displaystyle f(s) =\sum_{i=1}^{s} \binom{s-1}{i-1}\binom{s}{i}((i-1)!)^2 f(s-i)$

一股卷积的味道扑面而来

$\displaystyle f(s) =\sum_{i=1}^{s} \frac{(s-1)!}{(s-i)!(i-1)!}\frac{s!}{(s-i)!i!}((i-1)!)^2f(s-i)$

$\displaystyle f(s) =s!(s-1)!\sum_{i=1}^{s} \frac{1}{i}\frac{f(s-i)}{((s-i)!)^2}$

令 $\displaystyle g(i) = \frac{1}{i}, i>0,g(0)=0$

令 $\displaystyle h(i) = \frac{f(i)}{(i!)^2}$

$f(s)=s!(s-1)! (g\star h)[s]$

分治卷积就没了?

代码

https://atcoder.jp/contests/abc318/submissions/49633712

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
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
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;}
const int N=524288; // 1<<19
mint fac[N+10]={1};
mint ifac[N+10];

vector<mint> g(N+10,0); // 1/i, g(0)=0
vector<mint> f(N+10,0); // ans
vector<mint> h(N+10,0); // h[i]=f[i]/(i!i!)

// $f(s)=s!(s-1)! (g\star h)[s]$
void calc(int l,int r) { // [l,r)
  assert(r-1 <= N);
  if(l+1==r){
    if(l == 0) {
      f[0] = 1;
      h[0] = 1;
    }else{
      f[l] *= fac[l]*fac[l-1]; // 未到点之前都是 g * h
      h[l] = f[l]*ifac[l]*ifac[l];
    }
    return ;
  }
  int mid = (l+r)/2;
  calc(l,mid);
  // [l,mid) -> [mid,r)
  vector<mint> _h;
  rep(i,l,mid) _h.push_back(h[i]); // [l,mid)
  vector<mint> _g;
  rep(i,0,r-l) _g.push_back(g[i]); // [0,r-l)
  auto res = atcoder::convolution(_h,_g);
  rep(i,mid,r) f[i] += res[i-l];
  calc(mid,r);
}

int main(){
  rep(i,1,N+1) fac[i]=fac[i-1]*i;
  ifac[N] = fac[N].pow(MOD-2);
  per(i,0,N) ifac[i]=ifac[i+1]*(i+1);
  rep(i,1,N+1) g[i]=ifac[i]*fac[i-1];
  int n=read();
  mint ans = fac[n]*fac[n] + fac[n]; // all(n!n!) - alice - bob + alice&bob(n!)
  int bound = 1;
  while(bound <= n) bound*=2;
  calc(0, bound);
  ans -= 2*f[n];
  printf("%d\n",ans.val());
  return 0;
}

参考

Round-square tree https://www.cnblogs.com/luckyblock/p/14427288.html

https://atcoder.jp/contests/abc318/editorial

总结

G: 网络流 不熟中的不熟

Ex: 可能和熟练有关系吧，感觉Ex在我熟练下非常流畅（但编码很慢）自己做出来了，比G简单