Atcoder abc306

發表於 2023-06-29 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘

G(树,gcd)Ex(容斥原理,bitdp)

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

G - Return to 1

n点,m有向边

从1开始，每次从当前点选一条边移动，问$10^{10^{100}}$次时能否回到1

n,m 2e5

1024mb

我的思路

次数巨大，如果走k1次回到1，k2次回到1

那么可以 gcd(k1,k2)次的足够大的倍数回到1，因为问题中的次数巨大，所以 ak1+bk2=c gcd(k1,k2) = 10^{10^{100}}能找到正解

所以问题是能否找到两个不同的次数的 gcd 只有2和5的因子

一个不会证明的想法是，计算从1出发到达每个点的不超过2种距离，和逆向从1倒退不超过2种距离

这样每个点可以得到2x2种从1到1的距离

对所有距离做gcd看看是否只有 2和5的因子

但是这个做法，正确性感觉不会证明

题解

首先只保留和1强连通的点，（一个显然的化简）

同样的结论，所有包含1的环的长度的gcd 是这个巨大的数V的因子即是Yes

这里还证明了一下，其实说白了就是，能实现gcd,然后 V=lcm * 大的数 + gcd * 小的数, 系数展开能保证非负

然而所有环可能无限集合，考虑以1为根从图种任意构造一个生成树

对于质因子p, 所以如果有回边长度不是p的倍数，那么gcd中就不会包含p

因为,剩余点都是1可达和和可达1的，那么考虑 1-> u -> (多次环)-> u -> 1那么长度为1->u->1 + k 环,

显然 gcd(a+kb),k=0..\infity = gcd(a,b)

然而还有更弱限制的更强结论，只关心深度

不需要是回边，只需要是非树边 u->v

那么显然有两条路径 1->(树边)->v->任意->1,1->(树边)->u->(非树边)->v->任意->1

gcd(两条路径) = gcd(d[v] + len[v..1],d[u] + 1 + len[v..1])

= gcd(路径1/路径2, d[u]+1-d[v])

这样就简化成只和深度有关了，而且注意到本身路径也是最后会涉及指向1的边, 所以至少存在一个 (纯树边 + u->1)

Ex - Balance Scale

长 N的 x[1…N] 具体未知

比较权重M次

S=””

第i次比较, x[Ai]放左侧, x[Bi]放右侧, S += “>/=/<”

N [1,17]

1<= ai < bi <= N

1024mb

问对于所有不同的x, 能产生多少不同的S, mod 998244353

我的思路

也就是你可以钦定出多少个 ai,bi 的大小关系

看起来如果先做等于钦定（复杂度？），是不会有任何冲突的

做完等于钦定以后，那么就可以合并一下，剩下的x[ai],x[bi]全部不等, 不等的话只需要满足拓扑关系(无环)即可

首先想一下钦定等号

f(n) = 和1相等的选i个, binom(n-1,i) * 剩余的和1不等的方案数f(n-1-i)

$f(n) = \sum_{i\in[0,n-1]} \binom{n-1}{i} f(n-1-i)$

还是很大

f = [0] * 20
f[0]=1
f[1]=1

def binom(n,m):
    r = 1
    for i in range(1,m+1):
        r *= (n+1-i)
        r //= i
    return r


for i in range(2,18):
    for j in range(0,i):
        f[i] += binom(i-1,j) * f[i-1-j]
    print(i,f[i])

# 2 2
# 3 5
# 4 15
# 5 52
# 6 203
# 7 877
# 8 4140
# 9 21147
# 10 115975
# 11 678570
# 12 4213597
# 13 27644437
# 14 190899322
# 15 1382958545
# 16 10480142147
# 17 82864869804

另一个就是每次钦定最小的值，那一个问题是状态大概也是17!,

在最小的时候如果有相连的和它相等，则同时钦定，而没有链接的“相等”实际上不会影响

而相连的只考虑index更大的，这样能完成去重吗?

1-2,3-4

1<2,3<4

1和3 都是可以最小的时候

另一个点就是，如果是多个连通块，连通块之间不影响

所以考虑的只需要连通块内的方案数，连通块之间方案数相乘即可

如果，连通块有桥

显然桥可以大于/ 小于 /等于，去掉桥两边互不影响

3 * f(左连通块) * f(右连通块)

这个角度思考就是，找一个小割？？？

对应的，就是如果点u 有一系列小于点v,等于点u’,大于点w

那么

每个 v到u’路径至少一个小于

每个 v到w路径至少一个小于

每个 u’到w路径至少一个小于

想不出任何有效的

题解

题意等价

无向图N点M边

对于所有u-v, 要么正向边，要么反向边，要么合并点

问有多少中方案最终是DAG，

使用 bit DP (Dynamic Programming), 逐个删除入度为0 的点

然而当点集被删除, 如果剩余点集合还有入度为零的 0, 会重复统计，需要想办法避免

当删除一个点集, 被删除的需要是一个连通块(否则其中会有非0入度.)

这里对于一个点集，容斥的属性的定义是一个连通块为最小点

例如 (1-2-3-4)

如果对于一个实际的图中 1和3是最小点

那么在统计时分别被 (1是最小点，3是最小点，1是最小点且 3是最小点) 进行统计

这样的话就是简单的容斥了

这里要注意的是 (1-2-3-4), 如果1-2是最小点，那么因为1-2是连通块，所以只会被（1-2 是最小点统计)

所以 dp[mask] = dp[mask - submask] * (-1)^{连通块个数(submask)+1}

代码

https://atcoder.jp/contests/abc306/submissions/43311499

#include <bits/stdc++.h>
#include <atcoder/modint>
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++)
ll read(){ll r;scanf("%lld",&r);return r;}

class dsu{
public:
  vector<int> f;
  dsu(int sz){
    f = vector<int>(sz);
    iota(begin(f),end(f),0);
  }
  int fa(int u){ return (u == f[u])?u:(f[u]=fa(f[u])); }
  bool same(int u,int v){ return fa(u) == fa(v); }
  void merge(int u,int v){ f[fa(u)]=fa(v); }
};


int main(){
  int n=read();
  int m=read();
  vector<pair<int,int> > eg;
  rep(i,0,m)  eg.push_back({read()-1,read()-1});

  vector<int> comp(1<<n);
  vector<int> popcnt(1<<n);
  rep(i,1,1<<n){
    int res = popcnt[i]=popcnt[i&(i-1)]+1;
    dsu uf(n);
    for(auto [u,v]: eg) if(((i>>u)&1) and ((i>>v)&1) and !uf.same(u,v) ){
      uf.merge(u,v);
      res--;
    }
    comp[i]=res;
  }

  vector<mint> dp(1<<n,0);
  dp[0]=1;
  rep(i,1,1<<n) for(int j=(((1<<n)-1)&i);j;j=((j-1)&i)) {
    dp[i] += dp[i-j] * ((comp[j]&1)?1:-1);
  }
  printf("%d\n",dp[(1<<n)-1].val());
  return 0;
}

总结

想到了包含1的边长和gcd, 卡在了如何计算“所有路径的 gcd”，感觉知识点还是树+回边/跨边

等价题意也想得到

剩下就是并查集，子集遍历和容斥原理

不熟的还是容斥原理，其实不应该想不到的

参考

官方题解