Atcoder arc144

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