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
2s
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
我错哪里了????????????????????????????????????????????????
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
| #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];
mint f[N+1][MXEDGE+1];
mint g[N+1][MXEDGE+1];
mint p[N+1];
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);
rep(i0,1,i+1) rep(j0,0,j+1) if(i0+j0 != i+j) rep(c0,0,min(i0*j0,c)+1) {
h[i][j][c] -= h[i0][j0][c0]*binom(i-1,i0-1)*binom(j,j0)*binom((i-i0)*(j-j0),c-c0);
}
}
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;
}
|