Atcoder abc247

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
G(费用流)Ex(斯特林数,生成函数)

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

G - Dream Team

n个人第i个, 有值Ai,Bi,Ci

考虑从中选一些

满足Ai,Bi两两不同

对于所有可能的构成 人数 = 1…k

求最大的Ci的和

范围

n 3e4

ai, bi, [1,150]

ci [1,1e9]

2s

1024mb

我的思路

emmmm, 这个ai,bi 这么小, 但感觉又像费用流+限流?

ai,bi建立点

S->ai 每个1容量,0代价

bi->T, 每个1容量,0代价

中间就是ai->bi, -Ci 代价, 然后限流让总代价小

然后为了不能让代价为负, 所以全部+Max(Ci)

最后答案 - flow * max(Ci)?

似乎就没了

代码

https://atcoder.jp/contests/abc247/submissions/35077835

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
#include <bits/stdc++.h>
#include <atcoder/mincostflow>
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(){
  int n = read(); // 3e4
  const int N = 150;
  const int S = N*2;
  const int T = S+1;
  atcoder::mcf_graph<ll,ll> g(T+1);
  rep(i,0,N) g.add_edge(S,i,1,0);
  rep(i,0,N) g.add_edge(N+i,T,1,0);
  ll MAX = 1e9;
  rep(i,0,n){
    int a = read()-1;
    int b = read()-1 + N;
    int c = read();
    g.add_edge(a,b,1,MAX-c);
  }
  auto points = g.slope(S,T); // 包含{0,0}
  vector<pair<ll,ll>> ans;
  for(auto [f1,c1]:points){
    if(ans.size() != 0 && ans.back().first+1 != f1){
      auto [f0,c0] = ans.back();
      rep(f,f0+1,f1) ans.push_back({f,c0 + (c1-c0)/(f1-f0)*(f-f0)}); // [f0+1..f1-1]
    }
    ans.push_back({f1,c1});
  }
  printf("%d\n",(int)ans.size()-1);
  rep(i,1,ans.size()) printf("%lld\n",MAX*ans[i].first - ans[i].second);
  return 0;
}

Ex - Rearranging Problem

N 个人

第i个颜色ci

重复k次: 选两个不同人交换这两个人的位置

要初始 的n个颜色,和结束后的n个颜色,保持一致

问最终的排列有多少种 mod 998244353 (不是多少种交换方案)

范围

n 2e5

k [1,1e9]

4s

1024mb

我的思路

就是 和值没关系, 就是颜色的球, 换来换去,最后看颜色还是一样

如果能颜色分开讨论

一次交换

1: 一个颜色没有影响(外部交换或内部交换)
2: 一个目标位置变成非目标位置, 一个在位置的当前颜色 和 一个不在位置的异色
3: 非目标位置变成目标位置, 一个在位置的异色 和一个 不再位置的当前颜色

问题是颜色之间, 1和2似乎还好, 但是3 的话,还要跟踪?

另一个类似的就是, 颜色 = {坐标集合}

每次就是不同或同色之间的两个坐标 交换

那么要保持 最后集合还原

有一个优点是, 这样每个颜色对应集合的大小不会变, 所以如果发生了集合内部交换, 那么看作一个不影响状态的操作, 且方案数是一个定值

问题是跨集合的一次交换 并无法跟踪?

好像又读错题了, 不是问有多少交换方案而是k次后有多少个结果的排列

题解

首先证明一个引理, 如果把 i->Pi 连边, 那么 每次做交换pi,pj 对于图来说,环的个数增1或减1

这个在排列中很长见了

证明: 其实就分两种, 交换的本来是一个环还是不是一个环, 所以显然

因此

排列能做k次交换后变成(1…N) 也就是 环的数量 N-c <= k, 且(N-c) ==k (mod 2), (相当于每次最多少一个环

所以就是对于颜色相同的计算每种环的个数,

dp[i][j] = 长度为i的 形成了j个环的方案数

dp[i][j] = dp[i-1][j-1](第i个单独成环) + (i-1) dp[i-1][j] (插入到某个环的某个位置)

这就是第一类斯特林数

但这里也可以把 颜色混着考虑

dp[i][j] 表示前i个 构成环为j 的方案数

dp[i][j] = dp[i-1][j-1](第i个单独成环) + dp[i-1][j] * 前i-1个中和第i个颜色相同的个数

写成生成函数就是

$F_i(x) = xF_{i-1}(x) + c[i] F_{i-1}(x)$

$F_i(x) = (c[i] + x) F_{i-1}(x)$

就是$c[i] + x$ 和$F_{i-1}(x)$的卷积

顺序算肯定不行, 不过卷积有结合率, 所以考虑归并式计算

代码

https://atcoder.jp/contests/abc247/submissions/35148028

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>
#include <atcoder/convolution>
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 main() {
  int N = read();
  int K = read();
  vector<int> c(N + 1); // c[color] = 前面color的个数
  vector<vector<mint>> f; // 每次要卷积的
  rep(i,0,N){
    int x = read();
    f.push_back({c[x]++, 1}); // c[i] + x = c[i] * x^0 + 1 * x^1
  }

  while((int)f.size() > 1) { // 归并式卷积, 每次 [i*2,i*2+1] 卷积
    vector<vector<mint>> nxt;
    rep(i,0,f.size()/2) nxt.push_back(atcoder::convolution(f[i*2], f[i*2+1]));
    if (f.size() % 2) nxt.push_back(f.back());
    f = nxt;
  }
  mint ans = 0;
  rep(c,0,f[0].size()) if (N-c <= K and K%2 == (N - c) % 2) ans += f[0][c];
  printf("%d\n",ans.val());
}

总结

G

从完全不会费用流,到补atcoder遇到两三次, 这种入门题目现在似乎会了

虽然这题评分也就2100+

Ex

学了下第一类斯特林数

感觉这种 递推和卷积的关系又学了一点

参考

官方题解

stirling