Atcoder abc241

發表於 2022-09-18 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 1.9k 所需閱讀時間 ≈ 6 分鐘

G(网络流)Ex(生成函数)

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

G - Round Robin

n 个人

两两之间打比赛

已知已经结束了m场,每场wi赢,li输

问如果所有比赛结束后可能成为赢得比其它人都多的可能的id有哪些?

范围

n 50

1024mb

我的思路

如果一个人目前全胜,那当然可能

那如果一个人输过,那么可能是比其他所有人多吗?

显然是 n(n-1)/2 场比赛, 那么有n(n-1)/2个胜场, n(n-1)/2个负场

如果最多的t场,其它最多t-1场, t + (t-1)(n-1) >= n(n-1)/2

t >= (n-1)(n+2)/2n = (n-1)(1/2+1/n)

看起来似乎不一定要全胜

试一试

 12345
1 yyyx
2x yxy
3xx yy
4xyx y
5yxxx

这样的话 1胜3也是胜最多的

看数据量n 50, n(n-1)/2 = 1225

看起来能接受n^4

既然只讨论可能性, 那么不妨直接贪心这个人赢得最多, 得到他赢的次数t

那么变成剩下的点组成的图,能否让最大胜利次数 < t

感觉dp点或者dp边, 都不知道怎么处理互相关联的问题, 怎么做局部性

以及另外一个问题是, 如果剩下的点没有边已经确定,那么最小的胜利局数是怎么去分配边

毫无头绪

题解

网络流

还是每个人单独讨论

首先选个要判断的人, 让它为确定的比赛赢了剩下所有人, t等于他的胜利次数

源S

汇T

Aij代表i和j的比赛

Bi表示玩家i

S -> Aij, 容量1

i,j的比赛

i赢,则 Aij->Bi, 容量1

j赢,则 Aij->Bj, 容量1

未打比赛,则Aij->Bi, Aij->Bj

Bi->T, 容量 t-1

求S->T 最大流, 如果是 N(N-1)/2 即可

意义

首先S->Aij 表示每一场比赛,

Aij->B?, 表示对应的胜利方

B?->T 表示每个人胜利次数不大于t-1

最大流意味着满足限制的最大场次 <= n(n-1)/2

因此O(n * n^3 = n^4) 可完成

代码

https://atcoder.jp/contests/abc241/submissions/34983297

#include <bits/stdc++.h>
#include <atcoder/maxflow>
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

int wl[60][60]; // win lose, [i win j = 1], [i lose j] = -1, no result = 0
int n;

bool ok(int winner){
  int c = 0; // win count
  rep(i,0,n) if(i!=winner) c += wl[winner][i] >= 0;
  if(!c) return false;
  const int a = n*(n-1)/2;
  auto g = atcoder::mf_graph<int>(2+a+n); // S + T + n(n-1)/2 + n
  const int S = 0;
  const int T = 1;
  rep(i,0,a) g.add_edge(S,i+2,1); // S->Aij 
  int x = 2;
  rep(i,0,n) rep(j,i+1,n){
    if(wl[i][j] == 1){ // i赢,则 Aij->Bi, 容量1
      g.add_edge(x,2+a+i,1);
    }else if(wl[i][j] == -1){ // j赢,则 Aij->Bj, 容量1
      g.add_edge(x,2+a+j,1);
    }else if(i == winner || j == winner){ // 未打比赛, 但目前有一个是winner 要赢
      g.add_edge(x,2+a+winner,1);
    }else{ // == 0 未打比赛,则Aij->Bi, Aij->Bj
      g.add_edge(x,2+a+i,1);
      g.add_edge(x,2+a+j,1);
    }
    x++;
  }
  rep(i,0,n) g.add_edge(2+a+i,T, i == winner?c:c-1); // Bi->T, 容量 c-1
  return g.flow(S,T) == a;//  求S->T 最大流, 如果是 N(N-1)/2 即可
}

int main(){
  n = read();
  int m = read();
  while(m--){
    int w = read()-1;
    int l = read()-1;
    wl[w][l] = 1;
    wl[l][w] = -1;
  }
  rep(i,0,n) if(ok(i)) printf("%d ",i+1);
  return 0;
}

Ex - Card Deck Score

有N种卡片,写着Ai的卡片有Bi张

从这些卡片中选M张的分数 = 上面数字乘积

同样数字的卡片无法区分, 找所有可能的选取方式的分数和 mod 998244353

范围

n 16

m 1e^18

ai [1,998244353)

bi [1,1e17]

ai != aj

我的思路

这n的大小, 很想bitdp

这m很大, 甚至不能拆,

dp(i,j) = 前i个中选j个的所有方案的乘积和

dp(i,j) = sum dp(i-1,j-t) * power(a[i],t)

也没法

先上数学处理个n小的情况, 因为Bi > m 也没用, 所以令Bi = min(Bi,m), Bi <= m

n=1

a[0]^m

n=2

sum a[0]^i a[1]^{m-i}

0 <= i <= B0

0 <= m-i <= B1

min i = m-B1 <= i <= B0 = max i, 因为上面限制了Bi和m的大小关系

= a[0]^mini a[1]^{m-mini} * (1-(a[0]/a[1])^{maxi-mini+1})/(1-(a[0]/a[1]))

n = 3

???

(1 + a0 x^1 + a0^2 x^2 + … + a0^B0 x^B0)(1 + a1 x^1 + a1^2 x^2 + … + a1^B1 x^B1)…(1+an x^1+…+an^bn x^bn)

求 x^m 的系数

$= \frac{(1-(a_0x)^{B_0+1})(1-(a_1x)^{B_1+1})\cdots}{(1-a_0x)(1-a_1x)\cdots}$

显然上下可以考虑暴力展开,

然后再怎么搞呢, 做m阶导数?,

题解

恩也是生成方程, 直接得到式子

然后来了不管分子 !!!!!!!!, 考虑分母拆成多个分子为常数的分式和

$\frac{1}{(1-A_1x)(1-A_2x)\cdots (1-A_Nx)}=\frac{c_1}{1-A_1x}+ \frac{c_2}{1-A_2x}+\cdots+ \frac{c_N}{1-A_Nx}.$

而这个直接就拉格朗日插值就能算出

上式变成

$f(x) \equiv \bigl(1-(A_1x)^{B_1+1}\bigr)\bigl(1-(A_2x)^{B_2+1}\bigr)\cdots\bigl(1-(A_Nx)^{B_N+1}\bigr) \bigl(c_1(1+A_1x+(A_1x)^2+\cdots) +c_2(1+A_2x+(A_2x)^2+\cdots) +\cdots +c_N(1+A_Nx+(A_Nx)^2+\cdots) \bigr) \pmod{998244353}$

前面部分处理和我想的一样, 就暴力展开就完事

后面的部分其实是个展开问题, 2^N每个去后面 N组中找对应的幂次系数即可

代码

https://atcoder.jp/contests/abc241/submissions/34985025

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
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;}

#define N 16
mint a[N];
ll b[N];
mint c[N];
mint d[(1 << N)] = {1}; // d[mask] = prod -a[i]^(b[i]+1)
ll p[(1 << N)]; // p[mask] = sum b[...mask] + 1), 记录对应的幂次

int main() {
  int n = read(); // 16
  ll m = read(); // 1e18

  rep(i,0,n) {
    a[i] = read();
    b[i] = read()+1; // 分子是prod (1-a[i]^(b[i]+1))...
    mint x = -a[i].pow(b[i]);
    rep(j,0,(1 << i)) { // 高位到低位 对应 0 ~ N-1
      d[(1 << i) + j] = d[j] * x;
      p[(1 << i) + j] = p[j] + b[i];
    }
  }

  rep(i,0,n) { // 拉格朗日插值 算 拆分出来的常数倍数ci
    mint x = a[i].inv();
    c[i] = 1;
    rep(j,0,n) if (j!=i) c[i] *= (1 - a[j]*x);
    c[i] = c[i].inv();
  }

  mint ans = 0;
  // d[i]x^p[i] * c[j](a[j]x)^{m-p[i]}
  rep(i,0,(1<<n))if(p[i]<=m) rep(j,0,n) ans += a[j].pow(m-p[i])*c[j]*d[i];
  printf("%d\n",ans.val());
  return 0;
}

基于矩阵优化的多项式除法

在得到$= \frac{(1-(a_0x)^{B_0+1})(1-(a_1x)^{B_1+1})\cdots}{(1-a_0x)(1-a_1x)\cdots}$后也可以分子分母展开继续

这样分母是n次多项式,而分子直接拆开每个幂次单独处理

$t a^i = ? \cdot (1+k_1x^1+k_2x^2+\cdots+k_nx^n) $

要求?中$m-i$的系数

长度 n 的向量 $ v_i = (t,0,0,\cdots) $, 可以得到?中i次方系数是 $v_i[0]$

$v_{i+1} = v_i \cdot \left( \begin{array}{l} -k_1 & -k_2 & -k_3 & \cdots & -k_n \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \cdots \\ 0 & 0 & 0 & \cdots & 0 \end{array} \right) $

n^3 log m-i 快速幂搞一搞就行

Nero

https://atcoder.jp/contests/abc241/submissions/29706099

容斥完全不会

总结

网络流还是不熟, 虽然能感觉到分点讨论和贪心胜场和复杂度估计, 但是完全没看出是网络流的方向

感觉要过橙色的坎,网络流要足够熟练才行

生成方程完全不会, 生成方程又会一点

如何处理分母是一堆玩意儿的乘积

好消息是,似乎就缺这个分式乘积拆分的想法这个题我就搞出来了

矩阵加速多项式除法

参考

官方题解