Atcoder abc327

發表於 2023-11-04 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 2.6k 所需閱讀時間 ≈ 9 分鐘

G(容斥原理)

https://atcoder.jp/contests/abc327

G - Many Good Tuple Problems

(S,T) = 一对长度m值域[1,n]的序列

若存在长度n的 0/1 串x,使得所有i=1..m, x[s[i]] != x[t[i]], 那么称 s,t为一对好的

在所有的$n^{2m}$个方案中, 问好的序列有多少个 mod 998244353

n 30

m 1e9

1024mb

我的思路

D 题是判断是否是好的序列

其实s[i],t[i] 就是指定了一对x中0/1相反的位置，而如果多个si,ti连接了了一系列坐标，如果有合法方案那么这一系列被连着的坐标全部做0/1 翻转也合法，而和这个连通关系分离的位置，不会影响

所以s[i],t[i] 唯一需要满足的就是任何环都是偶数长度

然后n比较小，但不是很小不够bitmask,一半够bitmask

m很大，O(m)都过大

所以范围推方向大概要在 n上建立维度，而m直接用到计算里

f(sz) = sz个x连通的内部合法的方案数

g(sz) = sz个合法的方案数

$g(sz) = \sum_{t=1\cdots sz} \binom{sz-1}{t-1} f(t)g(sz-t)$, 这样sz中最小的点一定在f中，f中保证一块

这样的问题是这里缺失了m的性质

而且f似乎不太好算

改一下 f(vertex,edge)= vertex个点edge条边(可重边) 连通的方案数

g(vertex,edge)= vertex个点edge条边(可重边)的方案数

$\displaystyle g(i,j) = \sum_{t=1\cdots i,k=0\cdots j} \binom{i-1}{t-1} f(t,k)g(i-t,j-k)$

答案是$g(n,m)$

这样的问题是状态和转移代价都太大

改一下 f(vertex,edge)= vertex个有序点edge条无向边(无重边) 连通的方案数

g(vertex,edge)= vertex个有序点edge条无向边(无重边)的方案数

$\displaystyle g(i,j) = \sum_{t=1\cdots i,k=0\cdots j} \binom{i-1}{t-1} f(t,k)g(i-t,j-k)$

答案是$\displaystyle \sum_{c=0\cdots\frac{n(n-1)}{2}} g(n,c) p(m,c)2^m$

其中$p(m,c)$表示m个有序号球染色c种，每个颜色至少一个球的方案数,这里相当于选边，而$2^m$相当于边的正向和逆向

这样的好处是，当有了无重边的限制以后，$\mathrm{edge}\le \frac{\mathrm{vertex}(\mathrm{vertex}-1)}{2}$

两个问题 f怎么算?

f的想法是如果连通，那么钦定最小点为颜色0,和其它点的颜色0/1

可选的边有 count(0) * count(1) 条

再减去不连通的？

$h(i,j,c)=$i个有序0,j个有序1,c条边,所有连通的方案数

$l(i,j,c)=$i个有序0,j个有序1,c条边的任意方案数 = $\binom{ij}{c}$

$h(i,j,c) = l(i,j,c) - \sum \binom{i-1}{i_0-1}\binom{j}{j_0} h(i_0,j_0,c_0)l(i-1-i_0,j-j_0,c-c_0)$

其中$1+i_0+j_0 < i+j$

$f(i,j) = \sum_{t=0\cdots i-1} \binom{i-1}{t} h(1+t,i-(1+t),j)$

p怎么算?

m太大

p(m,c(n^2))

$p(m,c) = \sum_{t}\binom{m}{t}p(m-t,c-1)$

$\frac{p(m,c)}{m!} = \sum_{t}\frac{1}{t!}\frac{p(m-t,c-1)}{(m-t)!}$

令 $q(m,c) = \frac{p(m,c)}{m!}$

$q_{c} = q_{c-1} (e^x-1)$

$q_{c} = (e^x-1)^c$

$p(m,c) = m! x^m^c$

后面的$e^x-1$ 展开成幂级数，m太大不好算，不如二项式展开，直接上手

$\displaystyle p(m,c) = m! [x^m](\sum_{i=0}^c \binom{c}{i}(e^x)^i(-1)^{c-i})$

$\displaystyle p(m,c) = m! (\sum_{i=0}^c \binom{c}{i}\frac{i^m}{m!}(-1)^{c-i})$

$\displaystyle p(m,c) = (\sum_{i=0}^c \binom{c}{i}i^m(-1)^{c-i})$

h状态有O(n^4) ?, 如何快速算出, 还是打表?

没加-fsanitize=integer 1.2s
加了-fsanitize=integer 9s

f(i(n),j(n2)) 可以$O(n^4)$ 算出

g(i(n),j(n2)) 似乎需要O(n^5)

m个给定的，直接for c(n^2)就好了 O(n^4)能算出

综上

i有序0,j有序1,c边无重连:

$l(i,j,c)=\binom{ij}{c}$

i有序0,j有序1,c边无重连所有连通:

$\displaystyle h(i,j,c) = l(i,j,c) - \sum_{i_0=1}^{i}\sum_{j_0=0,i_0+j_0 < i+j}^{j}\sum_{c_0=0}^c \binom{i-1}{i_0-1}\binom{j}{j_0} h(i_0,j_0,c_0)l(i-i_0,j-j_0,c-c_0)$

i个有序点，j边，合法所有连通:

$\displaystyle f(i,j) = \sum_{t=1}^i \binom{i-1}{t-1} h(t,i-t,j)$

i个有序点，j边，合法：

$\displaystyle g(i,j) = \sum_{t=1}^{i}\sum_{k=0}^{j} \binom{i-1}{t-1} f(t,k)g(i-t,j-k)$

m个有序点上色c种，每个颜色至少一个点

$\displaystyle p(m,c) = (\sum_{i=0}^c \binom{c}{i}i^m(-1)^{c-i})$

最终答案为

$\displaystyle 2^m \sum_{c=0}^{\frac{n(n-1)}{2}} g(n,c) p(m,c)$

然而 pretest 对了2个点，错了两个点,emmmmmmmmmmmm

提交了一下还ac x21, wa x21

我错哪里了????????????????????????????????????????????????

#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++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N=30;
const int MXEDGE=225; // 最大边数
mint h[N+1][N+1][MXEDGE+1]; // h[有序0个数][有序1个数][无重边数]=全连通方案数
mint f[N+1][MXEDGE+1]; // f[有序点数][边数] = 合法全通方案数
mint g[N+1][MXEDGE+1]; // g[有序点数][边数] = 合法方案数
mint p[N+1]; // p[c] = m个有序点 上色c种，每种颜色至少一个点的方案数
mint fac[MXEDGE+10]={1};
mint ifac[MXEDGE+10]={1};
mint binom(int n,int m){return (m>n or m<0)?0:(fac[n]*ifac[m]*ifac[n-m]);}
int main(){
  rep(i,1,MXEDGE+1) fac[i]=fac[i-1]*i;
  ifac[MXEDGE]=fac[MXEDGE].inv();
  per(i,0,MXEDGE) ifac[i]=ifac[i+1]*(i+1);
  int n=read();
  int m=read();
  rep(i,1,N+1) rep(j,0,N+1-i) rep(c,0,i*j+1){
    h[i][j][c] = binom(i*j,c); // 不重复任意连c条
    rep(i0,1,i+1) rep(j0,0,j+1) if(i0+j0 != i+j) rep(c0,0,min(i0*j0,c)+1) { // 与最小i相连的连通块
      h[i][j][c] -= h[i0][j0][c0]*binom(i-1,i0-1)*binom(j,j0)*binom((i-i0)*(j-j0),c-c0);
    }
  }
  // 没加-fsanitize 1.2s
  // 加了-fsanitize 9s
  rep(i,1,N+1) rep(j,0,MXEDGE+1) rep(t,1,i+1) f[i][j] += binom(i-1,t-1) * h[t][i-t][j];
  g[0][0] = 1;
  rep(i,1,N+1) rep(j,0,MXEDGE+1) rep(t,1,i+1) rep(k,0,j+1) g[i][j] += binom(i-1,t-1)*f[t][k]*g[i-t][j-k];
  vector<mint> impwr(MXEDGE+1);
  rep(i,0,MXEDGE+1) impwr[i] = mint(i).pow(m);
  rep(c,1,MXEDGE+1) rep(i,0,c+1) p[c] += binom(c,i) * impwr[i] * ((c-i)%2==0?1:-1);
  mint ans =0;
  rep(c,0,MXEDGE+1) ans += g[n][c]*p[c];
  printf("%d\n",(ans*mint(2).pow(m)).val());
  return 0;
}

题解

问题转化成 n点二分图，m条边的方案数$a(N,M)$

问题答案 $= 2^m a(n,m)$

对于只有点可区分的二分图来说

b(m,k) = k个盒子放m个可区分的球，盒子不为空的方案数$\displaystyle \sum_{i=1}^k (-1)^{k-i}\binom{k}{i}i^m$, 这里和我想的$p(m,c)$一样

f(n,m) = n点m边的方案数

$\displaystyle a(n,m) = \sum_{k=0}^{L} f(N,k)b(M,k)$

所以问题来到了如何求$f(N,0\cdots L)$

用了类似abc213g的容斥dp的方法

$g(n,m)=$ n点，m边的合法方案数

$\displaystyle g(n,m) =\sum_{i=0}^n\binom{n}{i}\binom{i(n-i)}{m}$ 相当于选择i个白色点，剩下黑色点，左边选点，右边选边

$h(n,m)=$在g的基础上增加连通的限制

$\displaystyle h(n,m)=g(n,m) - \sum_{i\in[1,n-1]}\sum_{j\in[0,m]}\binom{n-1}{i-1}h(i,j)g(n-i,m-j)$

i为包含n中最小点的选择方案

h的直接的值翻转顔色也是一个方案，所以除以2指定了最小顔色的方案

$\displaystyle f(n, m) = \frac{h(n,m)}{2} + \sum_{1 \leq i \lt n} \sum_{0 \leq j \leq m} \binom{n-1}{i-1} f(i, j) \frac{h(n-i,m-j)}{2}$

就没了

然后官方还给了两种基于生成函数的做法，Bostan-Mori (abc300ex)

代码

笑死 p的大小开小了，自己可以AC的

https://atcoder.jp/contests/abc327/submissions/49891988

#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++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N=30;
const int MXEDGE=225; // 最大边数
mint h[N+1][N+1][MXEDGE+1]; // h[有序0个数][有序1个数][无重边数]=全连通方案数
mint f[N+1][MXEDGE+1]; // f[有序点数][边数] = 合法全通方案数
mint g[N+1][MXEDGE+1]; // g[有序点数][边数] = 合法方案数
mint p[MXEDGE+1]; // p[c] = m个有序点 上色c种，每种颜色至少一个点的方案数 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 空间开错了
mint fac[MXEDGE+10]={1};
mint ifac[MXEDGE+10]={1};
mint binom(int n,int m){return (m>n or m<0)?0:(fac[n]*ifac[m]*ifac[n-m]);}
int main(){
  rep(i,1,MXEDGE+1) fac[i]=fac[i-1]*i;
  ifac[MXEDGE]=fac[MXEDGE].inv();
  per(i,0,MXEDGE) ifac[i]=ifac[i+1]*(i+1);
  int n=read();
  int m=read();
  rep(i,1,N+1) rep(j,0,N+1-i) rep(c,0,i*j+1){
    h[i][j][c] = binom(i*j,c); // 不重复任意连c条
    rep(i0,1,i+1) rep(j0,0,j+1) if(i0+j0 != i+j) rep(c0,0,min(i0*j0,c)+1) { // 与最小i相连的连通块
      h[i][j][c] -= h[i0][j0][c0]*binom(i-1,i0-1)*binom(j,j0)*binom((i-i0)*(j-j0),c-c0);
    }
  }
  // 没加-fsanitize 1.2s
  // 加了-fsanitize 9s
  rep(i,1,N+1) rep(j,0,MXEDGE+1) rep(t,1,i+1) f[i][j] += binom(i-1,t-1) * h[t][i-t][j];
  g[0][0] = 1;
  rep(i,1,N+1) rep(j,0,MXEDGE+1) rep(t,1,i+1) rep(k,0,j+1) g[i][j] += binom(i-1,t-1)*f[t][k]*g[i-t][j-k];
  vector<mint> impwr(MXEDGE+1);
  rep(i,0,MXEDGE+1) impwr[i] = mint(i).pow(m);
  rep(c,1,MXEDGE+1) rep(i,0,c+1) p[c] += binom(c,i) * impwr[i] * ((c-i)%2==0?1:-1);
  mint ans =0;
  rep(c,0,MXEDGE+1) ans += g[n][c]*p[c];
  printf("%d\n",(ans*mint(2).pow(m)).val());
  return 0;
}

总结

整体的思路顺序基本没有问题，所以我错哪了？？？？？？？？？？好家伙 p的size开错了，这虽然红题，从难度上自己也能AC的，感觉题目的过程看起来比我简洁一些吗？

用了abc213g的容斥dp的方法，我也用了啊

string number还是不熟，虽然自己推出来了,b=stirling number * m! 有关