Atcoder abc317

發表於 更新於 分類於 ， Disqus： 文章字數： 2.3k 所需閱讀時間 ≈ 8 分鐘
G(Hall's theorem)Ex(生成函数,矩阵)

https://atcoder.jp/contests/abc317

G - Rearranging

n x m 矩阵，一共含有 1..n 都有m个

n,m \in [1,100]

对于每一行，行内可以随意重排列

问是否有办法让每一列都是 1..n 各出现一次, 如果有给出方案

2s

1024mb

我的思路

第一直觉是一定有方法

想法是每次确定一列

每次找单行中出现次数最多的减去1,

然后 剩余行中未被选择的最多的减去1

如果这个方案是可行的，那么就能变成 列数规模减1的 同样子问题

所以需要证明 一定可行，或者找到反例

1
2
3
4
5
11144
22244
33345
55223
11553

是一个反例，这样会先选1,2,3 就无法选到4了, 但同时它也有方案

1
2
3
4
5
11144
24422
43335
52253
35511

另一个想法是 从值看，如果一个值占满了一行，那么这个值就不需要考虑如何分配了，变成行-=1的子问题

如果 一个值未占满一行，那么至少有2行有它

然后（一行，值）选不选，作为状态 似乎能构成2-sat问题

如果能证明这个2-sat问题一定有解，那么原问题就有解，如果证明不了，那当无解时，并不能证明不能递归下降就是无解

感觉需要智力来完成构造？但我没有智力

题解

左边n个点表示行，右边n个点表示值

每个 i->a[i,j] 形成边，可以重边

这样进行一次完美匹配，则对应了一次选列

证明总存在答案

直接 hall定理

首先选颜色数 连的行数 总是 $\ge$颜色数，因为有颜色数 * m（每个颜色个数）个值， 至少要 颜色数 * m（每个颜色个数）/ m(列数)行来放，

所以总有 完美匹配的方案，那么去掉完美匹配方案就是子问题

那么如何找完美匹配 就是简单的二分图最大匹配算法了

代码

https://atcoder.jp/contests/abc317/submissions/49622324

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
#include <bits/stdc++.h>
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;}
class MaxFlow{
  vector<vector<tuple<int,int>> > G; // {vertex idx,edge idx}
  vector<ll> edge; // 边剩余容量, 偶数正向边, 偶数+1 的逆向边
  vector<int> d; // bfs 距离
public:
  ll INF=0x3f3f3f3f3f3f3f3f;
  // 点范围: [0,n)
  MaxFlow(int n/*点数*/){ G.resize(n); }
  void path(int u,int v,ll cap){ // u->v, 容量
    assert(u != v); // 禁止自环
    assert(0 <= u and u < (int)G.size());
    assert(0 <= v and v < (int)G.size());
    G[u].push_back({v,(int)edge.size()}); edge.push_back(cap); // 正向边
    G[v].push_back({u,(int)edge.size()}); edge.push_back(0); // 反向边
  }
  int dfs(int u,int en, ll flow, vector<tuple<int,int,int,ll> >&flows/*实际流u,v,eid,f*/){
    if (u == en) return flow;
    for(auto [v,eid]:G[u]) if(edge[eid] != 0 and d[v] == d[u]+1) { // 按照bfs距离走
      int r = dfs(v,en,min(flow,edge[eid]),flows); // 实际流量
      if(r) {
        flows.push_back({u,v,eid,r});
        edge[eid  ]-=r;
        edge[eid^1]+=r;
        return r;
      }
    }
    d[u] = 0; // 标记无效 替代vis
    return 0;
  }
  bool bfs(int st,int en){ // 计算bfs距离
    d = vector<int>(G.size(),-1);
    vector<int> q = {st};
    d[st] = 0;
    rep(i,0,q.size()){
      int u = q[i];
      for(auto [v,eid]: G[u]) if(d[v] == -1 and edge[eid] != 0){ // u -> v 有正容量路径
        d[v] = d[u] +1;
        q.push_back(v);
      }
    }
    return d[en] >= 0; // en可达
  }
  // return maxflow, array<tuple<from,to,eid,flow>>
  pair<ll,vector<tuple<int,int,int,ll> > > calc(int st,int en){ // 一次性计算 st -> en
    int ans = 0;
     vector<tuple<int,int,int,ll> > flows;
    while(bfs(st, en)) ans += dfs(st, en, INF,flows);
    return {ans,flows};
  }
  void update_edge(int eid,ll cap){
    edge[eid] = cap;
  }
};

int ans[110][110];
int main(){
  // [0,n) row
  // [n,2n) value
  // S=2n,T=2n+1
  int n = read();
  int m = read();
  int S=2*n;
  int T=S+1;
  auto mf = MaxFlow(T+1);
  rep(i,0,n) mf.path(S,i,1); // S->X_{row}
  rep(i,0,n) mf.path(i+n,T,1); // Y_{val} -> T
  rep(i,0,n) rep(j,0,m) mf.path(i,n+read()-1,1); // X_{row} -> Y_{val}
  rep(j,0,m){
    auto [f,flows] = mf.calc(S,T);
    assert(f==n);
    for(auto [row,val,eid,flow]:flows) if(row < n and val >= n and val < 2*n){ // row -> val
      mf.update_edge(eid^1,0); // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      ans[row][j] = val-n+1;
    }
    rep(i,0,2*n) { // S->X, Y->T
      mf.update_edge(i*2  ,1);
      mf.update_edge(i*2+1,0);
    }
  }
  printf("Yes\n");
  rep(i,0,n) rep(j,0,m) printf("%d%c",ans[i][j]," \n"[j+1==m]);
  return 0;
}

Ex - Walk

n点有向图，无重边，但可能自环

然后对于任意边 $s\to t$, 要么$t=1$, 要么点的下标$t-s\in[0,2]$

问有多少种方案 从1开始，到n结束，恰好k次, mod 998244353

n 5e4

k 5e5

8s

1024mb

我的思路

首先所有边都是前进边没有回边

所以到任何点至多使用了一次从1的距离跳跃，剩下的就是 自环/+1/+2

dp[i][step] = dp[1][step-1]+dp[i][step-1]+ dp[i-1][step-1] + dp[i-2][step-2] ,

然后每个加项还要乘上 它们对应的边是否存在

注意没有重边对于i=2,=3稍微处理一下

这样的做法是O(nk)的 显然mle+tle

然后想的就是生成函数

$f_i(x) = \sum_{j} A_{i,j} x^j$

$f_i = a_i\cdot f_ix+d_i\cdot f_1x+b_{i-1}\cdot f_{i-1}x+c_{i-2}\cdot f_{i-2}x$

这让我想到了 矩阵乘法

$[f_i,f_{i-1},f_1] \to [f_{i+1},f_{i},f_1]$， 对于自环, 就是分母乘上$(1-a_ix)$,

1
2
3
b[i-1]x   1 0
c[i-2]x 0 0
d[i]x       0 1

然后因为矩阵乘法的结合率，可以就是二分/分治，这样每次的最高x次方不超过倍长度

读错题了，艹艹艹艹艹艹艹艹艹艹艹艹艹艹，d[i]是n->1 不是1->n 那就相对麻烦了，有回边

不过也好，因为所有的环都经过1,所以需要计算 1...[not 1]...1的 长度 => 个数

这样 矩阵 改动一下

1
[f_i,f_i,sum 首位是1中间非1的环]

$f_i = a_i\cdot f_ix+b_{i-1}\cdot f_{i-1}x+c_{i-2}\cdot f_{i-2}x$ 只计算无环的情况

1
2
3
b[i-1]x/(1-a[i]x)    1   d[i]x b[i-1]x/(1-a[i]x)
c[i-2]x/(1-a[i]x)    0   d[i]x c[i-2]x/(1-a[i]x)
0                    0    1

这样 分母单独算，似乎就过了？

代码

还真过了

https://atcoder.jp/contests/abc317/submissions/49627904

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
#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;}
int a[50010], b[50010], c[50010], d[50010];
using poly = vector<mint>;
using matrix = vector<vector<poly> >; //
poly norm(poly p){
  while(p.size() > 1 and p.back() == 0) p.pop_back();
  return p;
}
poly operator*(const poly&p0,const poly&p1){
  return norm(atcoder::convolution(p0,p1));
}
poly operator+(const poly&p0,const poly&p1){
  poly ret(max(p0.size(),p1.size()));
  rep(i,0,size(p0)) ret[i]+=p0[i];
  rep(i,0,size(p1)) ret[i]+=p1[i];
  return norm(ret);
}
poly operator-(const poly&p0,const poly&p1){
  poly ret(max(p0.size(),p1.size()));
  rep(i,0,size(p0)) ret[i]+=p0[i];
  rep(i,0,size(p1)) ret[i]-=p1[i];
  return norm(ret);
}

matrix operator*(const matrix&m0,const matrix&m1){
  matrix ret(m0.size());
  rep(i,0,m0.size()) {
    ret[i].resize(m1[0].size());
    rep(j,0,m1[0].size()) ret[i][j] = {0} ; // N x N, {0}
  }
  rep(i,0,m0.size()) rep(j,0,m1[0].size()) rep(k,0,m1.size()) ret[i][j] = ret[i][j]+m0[i][k]*m1[k][j];
  return ret;
}

void polyModn(poly&p,int n) { // return (this) mod x^n
  if((int)p.size()>n) p.resize(n);
}

poly polyInv(const poly&p, int n) { // return poly^{-1}, s.t. this poly^{-1} \equiv 1 \pmod{x^n}
  assert(p[0] != 0);
  poly r = {p[0].inv()};
  for(int pwr=1;pwr<n;pwr*=2){
    polyModn(r,pwr);
    r = r * (poly(vector<mint>{2}) - r * p);
  }
  polyModn(r,n);
  return r;
}

poly polypow(poly p,int pwr,int n){
  poly ret = {1};
  while(pwr){
    if(pwr&1) {
      ret = ret*p;
      polyModn(ret,n);
    }
    p = p*p;
    polyModn(p,n);
    pwr/=2;
  }
  return ret;
}

matrix top(int l,int r){ // [l,r)
  if(l+1==r){
    // b[i-1]x/(1-a[i]x) 1 d[i]x b[i-1]x/(1-a[i]x)
    // c[i-2]x/(1-a[i]x) 0 d[i]x c[i-2]x/(1-a[i]x)
    // 0                 0 1
    // 统一乘上分母 1-a[i]x
    poly fm = norm({1,-a[l]});
    auto ret =matrix{
      {poly{0,b[l-1]},fm     ,poly{0,0,b[l-1] and d[l]}},// from -1, not 1
      {poly{0,c[l-2]},poly{0},poly{0,0,c[l-2] and d[l]}},// from -2, not 1
      {poly{0}       ,poly{0},fm} // from 1 , 从1的来源的只看d
    };
    return ret;
  }
  int mid=(l+r)/2;
  return top(l,mid)*top(mid,r);
}
// 处理分母的部分
poly bot(int l,int r){ // [l,r)
  if(l+1==r) return norm({1,-a[l]});
  int mid=(l+r)/2;
  return bot(l,mid)*bot(mid,r);
}

int main(){
  int n=read();
  int k=read();
  rep(i,1,n+1) a[i]=read(); // self cycle
  rep(i,1,n+1) b[i]=read(); // i -> i+1
  rep(i,1,n+1) c[i]=read(); // i -> i+2
  rep(i,1,n+1) d[i]=read(); // 1 -> i
  poly f1 = poly{1};
  poly f0 = poly{0};
  poly cyc = poly{0,d[1]}; // 长度为1的环
  auto res = ((matrix{{f1,f0,cyc}}) * top(2,n+1)); // \prod matrix 2...n
  auto fm = bot(2,n+1);
  // res[0][0] 直达n
  // res[0][2] 1->not 1->1 的方案
  auto direct = res[0][0] * polyInv(fm,k+1);
  auto ct1    = res[0][2] * polyInv(fm,k+1);
  // assert ct1[0] == 0
  // {1} + ct1 + ct1^2 + ... + ct1^k
  // = (ct1^{k+1}-1) / (ct1-1)
  auto ans = direct * (polypow(ct1,k+1,k+1) - poly{1}) * (polyInv(ct1 - poly{1},k+1));
  printf("%d\n", (k < (int)ans.size() ? ans[k].val() : 0));
  return 0;
}

参考

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

总结

316 不知道为啥消失了

G: 感觉上是觉得总有解，但想不出如何证明, 转化成二分图匹配也没想到, hall’s theorem遇到过2次

hall’s theorem

不过好久都没有写最大流的题目了

Ex: 虽然写了很久，但自己写出了3426铜牌题，