orangejuice's blog

挂了请务必叫我

Posted on Edited on In

「CTSC2016」香山的树 (KMP+dp)

题目大意

对于所有的串，满足：

  1. 其是本身的最小循环同构。
  2. 其最小循环同构位置唯一。

给定一个这样的串，求其字典序在所有合法串中的 \(\text{rank}\)，以及求 \(\text{rank}=k\) 的串。

简要分析

这是一个暴力的做法，有一定优化空间。

约定 \(\Sigma\) 为字符集。

显然是要枚举答案，求出当前字符串在所有答案中的 \(\text{rank}\) ，不断增大答案 \(S\) 的字典序。

求出字典序 \(>S\) 的个数，考虑 \(\text{dp}\) 求解。

比较大小可以想到要不断进行前缀匹配，因此考虑 \(\text{kmp}\)。

因为要 \(\text{dp}\) 的是一个循环同构串，不妨直接扩展为无限循环的串，\(\text{dp}\) 一个 最小 的循环节。

不妨先考虑没有字典序限制的简单情形，也就是抛开 \(\text{kmp}\) 判断字典序，计算长度为 \(i\) 的方案数。

对于限制条件 2 ，等价于不存在循环分解，可以对于长度进行有关倍数的容斥，即 \(g_i=f_i-\sum_{d|i,d<i} g_d\)。

对于限制条件 \(1\)，不妨枚举一个无限循环串 \(S\) 的最优匹配位置为 \(st\)，然后 \(\text{dp}\) 一个长度为 \(i\) 的循环节。

显然要满足的条件是：

  1. \(\text{dp}\) 了 \(i\) 个字符之后匹配状态为 \(st\)。

  2. 在 \(\text{dp}\) 过程中如果 \(\text{kmp}\) 出现失配，必须满足当前字符更大。

    注意这里的边界情况，当匹配位置恰好等于 \(|S|\) 时，可能会将恰好为 \(S\) 的情况算入，因此要特判。

  3. 中途不能匹配到比 \(st\) 更大的位置。

同样的会出现两种重复计算：

  1. 串内出现了循环，即上文提到的容斥。

  2. 多个不同的开始位置都合法。

由于不存在循环，即每一个循环同构的位置都不同，考虑直接记录匹配过程中恰好为 \(st\) 的次数，在最终方案里除掉。

由以上思路，定义 \(f_{i,j,d}\) 表示当前 \(\text{dp}\) 了 \(i\) 位，匹配状态为 \(j\)，中途出现了 \(d\) 个恰好为 \(st\) 的匹配位置。

在求解完所有 \(f_{i,j,d}\) 后，先对于长度倍数进行容斥，由于多了一个维度，容斥时实际上变成了 \(f_{i,j,d}-f_{i,jk,dk}\) 的形式。随后再除以 \(d\) 算进答案。

可以得到一个 \(O(n^3|\Sigma|)\) 的暴力 dp，算上枚举起始位置，复杂度为 \(O(n^4|\Sigma|)\)。

由于还需要按位二分答案，所以复杂度为 \(O(n^5|\Sigma|\log |\Sigma|)\)，实际可以通过。

一个小优化：每次二分时，只有 \(st=|S|\) 或者 \(st=|S|-1\) 的部分需要重新 \(dp\) （即 \(st<|S|-1\) 时 \(S\) 的变化与 \(\text{dp}\) 值无关）。

因此实际复杂度为 \(O(n^4|\Sigma|\log |\Sigma|)\)。

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
#include<bits/stdc++.h>
using namespace std;

typedef __int128 ll;
//本地测试可以改成long long ，并且把下面的U=1e36改为U=1e18
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=52,S=26;
const ll U=1e36;

void chk(ll &a){ a>U && (a=U); }

int n,m;
ll k;
char s[N];
int nxt[N],trans[N][S];
void Init_KMP(){
	rep(i,2,m) {
		int j=nxt[i-1];
		while(j && s[i]!=s[j+1]) j=nxt[j];
		if(s[i]==s[j+1]) j++;
		nxt[i]=j;
	}
	rep(i,0,m) {
		rep(j,0,S-1) {
			int k=i,f=1;
			while(s[k+1]!=j+'a') {
				f&=j+'a'>s[k+1];
				if(!k) break;
				k=nxt[k];
			}
			if(s[k+1]==j+'a') k++;
			trans[i][j]=f?k:-1;
		}
	}
}

ll dp[N][N][N];
ll Ans[N];

ll Calc(int k=0){
	m=strlen(s+1),Init_KMP();
	ll ans=0;
	rep(st,(k?0:m-1),m) {
		Ans[st]=0;
		rep(i,0,n) rep(j,0,st) rep(d,0,n) dp[i][j][d]=0;
		dp[0][st][0]=1;
		rep(i,1,n) {
			rep(j,0,st) rep(d,0,i) if(dp[i-1][j][d]){ 
				rep(c,j==m?0:s[j+1]-'a',S-1) if(~trans[j][c]) {
					chk(dp[i][trans[j][c]][d+(trans[j][c]==st)]+=dp[i-1][j][d]);
				}
			}
		}
		rep(i,1,n) rep(d,0,n) if(dp[i][st][d]) {
			if(dp[i][st][d]==U) return U;
			rep(j,2,min(n/i,n/d)) dp[i*j][st][d*j]-=dp[i][st][d];
			if(i>m || st!=m) chk(Ans[st]+=dp[i][st][d]/d); // 特判了恰好为S的情况
		}
	}
	rep(i,0,m) chk(ans+=Ans[i]);
	return ans;
}

int main(){ 
	//freopen("treelabel.in","r",stdin),freopen("treelabel.out","w",stdout);
	scanf("%d%lld%s",&n,&k,s+1);
	k=Calc(1)-k+1;
	if(k<0) return puts("-1"),0;
	rep(i,1,n) {
		int l='a',r='a'+S-1,res=0;
		while(l<=r){
			int mid=(l+r)>>1;
			s[i]=mid,s[i+1]=0;
			if(Calc()>=k) res=mid,l=mid+1;
			else r=mid-1;
		}
		s[i]=res,s[i+1]=0;
		if(!res || Calc()==k) break;
	}
	puts(s+1);
}

Posted on Edited on In

UOJ Round#6 懒癌

题目大意

有\(n\)条狗，其中至少有一条得了懒癌。每个人可以看到一部分狗的情况，并且每天进行一轮推断

当它推断出自己的狗一定有懒癌时，就会将自己的狗枪毙，并且所有人停止推断。如果有多个人同时推断出则同枪毙

求在所有\(2^n-1\)种情况中，所有有狗被杀的情况中，一共过了多少天，枪毙了多少狗。


分析

首先考虑用状压\(dp\)来模拟所有的情况和转移，设\(dp_{S}\)表示集合\(S\)中的狗得了懒癌时的最小推断步数

我们考虑通过反推的方式进行转移，显然一个没有懒癌的狗永远不会被枪毙。

  1. 边界条件：当一个人能看到所有狗，并且其他狗都没有懒癌时，直接枪毙，\(dp_S=1\)

  2. 反证法：

    对于一个有懒癌的狗\(i\)进行反证

    1. 先假设自己的狗没有病
    2. 枚举所有可能的状态，即枚举所有看不到的狗是否得了病，得到后继状态集合\(\text{next}(S,i)\)
    3. 如果\(k\)步以内所有可能情况均已经达成了结束，在这个状态却没有，说明假设不成立，在\(k+1\)天就会枪毙自己的狗。

    此时，设所有可能状态集合为\(\text{next}(S,i)\)，则答案为\(dp_{S,i}=\max_{T\in\text{next}(S,i)}\{dp_T\}+1\)

  3. 总转移：\(\displaystyle dp_{S}=\min_{i\in S} \{\max_{T\in\text{next}(S,i)}\{dp_T\}+1\}\)

所有不会成环的状态均有结束状态（这里并没有处理枪毙了多少狗）


简化转移

从上面的转移式中容易看出：

对于\(U\subseteq V\)，一定有\(dp_{U}\leq dp_V\)

故在转移时，不再需要枚举看不到的狗是否得了病，只需要考虑它们全部得病的情况。


转移出现环的性质

对于每个\(i\)看不到\(j\)的关系（\(i\ne j\)），从\(i\)向\(j\)连一条边，如果第\(i\)条狗有懒癌，则第\(i\)个点为黑点，否则为白点。

考虑简化之后的转移的过程，转移后继有着怎样的特点：

  1. 选择了一个\(S\)中的元素\(i\)，并且将其删除；将\(i\)出边的所有点加入\(S\)
  2. \(S\)中的元素均没有出边时，才能够保证到达边界状态

故在建成的图上，对于一个大小\(>1\)的强连通分量（也就是存在环的分量）

一旦其中出现了黑点，该状态就永远无法到达边界状态

同样的，如果一个点能够到达一个环，那么这个点也不能是黑点

将这些非法点剔除之后，设新的图为包含\(n\)个节点的\(\text{DAG}\)


在\(\text{DAG}\)上统计答案

上文已经提到了转移过程在\(\text{DAG}\)上的体现，那么考虑一个状态如何到达边界：

  1. 选择某一个 没有其他黑点能到达 的黑点，将它删掉，加入它的出边

  2. 当\(\text{DAG}\)上不存在黑点时，状态结束，1过程进行的次数就是答案

  • 第一问

    只需要考虑每个点被进行1操作的次数。

    容易发现，如果有一个黑点能够到达\(i\)，\(i\)就会被操作一次。

    故只需要统计出有多少点能够到达\(i\)（包括\(i\)自己），设为\(f_i\)，答案就是\(\sum (2^{f_i}-1)2^{n-f_i}\)

  • 第二问

    显然我们需要统计每一条狗被枪毙的次数。

    考虑上面的转移对应着一个怎样的推导过程：

    1. 在一开始的集合枚举了一个点\(i\)，得到一个后继状态
    2. 经过一系列后继状态的转移到达边界，发现矛盾
    3. 一开始被枚举的那个\(i\)被枪毙

    那么被枪毙的狗，实际上就是 某一个 没有其他黑点能到达 的黑点（也就是一开始的转移式中枚举的每一个最优的\(i\)）。

    容易发现答案就是\(\sum 2^{n-f_i}\)

Posted on Edited on In

「BalticOI 2021 Day1」A Difficult Choice

题目大意

这是一道交互题，有一个长度为 \(n\) 且未知的正整数序列 \(a_i\)，保证其单调递增。

你可以用任意顺序询问其中至多 \(S\) 个数，并且对于给定的阈值 \(A\) 和大小 \(k\)，要求从 \(n\) 个数中选出 \(k\) 个数（不能重复），使得它们的和 \(\in [A,2A]\)。


Read more »

Posted on Edited on In

「BalticOI 2021 Day1」Inside information

题目大意

有 \(n\) 个集合 \(S_i\) ，一开始 \(S_i=\{i\}\)。

执行 \(m\) 个操作：

  1. 选择 \(u,v\) ，令 \(S_u,S_v:=S_u\cup S_v\)。
  2. 对于 \(u,x\)，回答 \([x\in S_u]\)。
  3. 对于 \(x\)，回答 \(\sum_i [x\in S_i]\)。

保证操作 \(1\) 恰好出现 \(n-1\) 次，且所有边 \((u,v)\) 构成一棵树。

分析

题目保证或操作构成一棵树，考虑一个熟悉的问题：

每次选择两个点连边，维护连通块中的点集。

用并查集+线段树合并处理。

Read more »

Posted on Edited on In

无标号有根树/无根树 计数

当然是从有根树开始啦

树计数容易想到递归进行，设 \(n\) 个节点有根树的 \(\text{OGF}\) 为 \(F(x)\)

我们考虑 \(F(x)\) 作为新根节点的子树的情况，这是一个可置换的背包问题，被称为 \(\text{Euler}\) 变换

不妨对于 \(F(x)\) 的每一项考虑，我们从 \(F_k\) 这么多种类的数中选择一些出来，然后组成背包

设 \(I=x^k\) ， \(n=F_k\) ，那么对于这一项的变换可以表示为

\(\displaystyle T(I,n)=\sum_{i=0}\binom{n}{i} (\sum_{j=1}^{\infty}I^j)^i=(\sum_{j=1}^{\infty}I^j+1)^n=\frac{1}{(1-I)^n}\)

那么得到 \(\text{Euler}\) 变换

\(\displaystyle \mathcal{E}(F(x))=\prod_{i=1}T(x^i,F_i)=\prod \frac{1}{(1-x^i)^{F_i}}\)

两边求 \(\ln\)

\(\displaystyle \ln \mathcal{E}(F(x))=\sum_i F_i\ln \frac{1}{(1-x^i)}\)

\(\displaystyle \ln \mathcal{E}(F(x))=\sum_i F_i(\sum_{j=1}\frac{x^{ij}}{j})\)

换循环

\(\displaystyle \ln \mathcal{E}(F(x))=\sum_i \frac{1}{i}(\sum_{j=1}F_j(x^i)^j)=\sum \frac{F(x^i)}{i}\)

\(\displaystyle \mathcal{E}(F(x))=\text{exp}(\sum \frac{F(x^i)}{i})\)

到这里我们得到了一个比较阳间的变换形式，那么 \(F(x)\) 的递归表示就是

\(F(x)=x\cdot \mathcal{E}(F(x))\)

考虑用牛顿迭代求解，设已经求出 \(G(x)=F(x)\mod x^n\) ，我们要求 \(F(x)\mod x^{2n}\)

而 \(\displaystyle \mathcal{E}(F(x))=\text{exp}(\sum \frac{F(x^i)}{i})\) 中 \(i\ge 2\) 的项都是已知的，可以在 \(O(n\ln n)\) 时间得到，不妨这些项为常数 \(\text{coef}\)

则方程为 \(x\cdot \text{exp}(F(x)+\text{coef})-F(x)=0\)

方程函数为 \(f(z)=xe^{z+\text{coef}}-z\)

\(f'(z)=xe^{z+\text{coef}}-1\)

故知 \(\displaystyle F(x)=G(x)-\frac{xe^{G(x)+\text{coef}}-G(x)}{xe^{G(x)+\text{coef}}-1}\)

(这里没有分治解法的。。。实际我也不会)

\[ \ \]

下面是无根树计数，考虑令重心为根即可

可以直接减掉存在一个子树 \(> \frac{n}{2}\) 的贡献，因为不会出现置换重复，可以将这个子树从原来的树上踢掉

剩下部分依然看成一棵有根树，也就是 \(F_i\cdot F_{n-i}(i>\frac{n}{2})\)

对于 \(2|n\) 的情况，重心可能有两个，此时要减去对称情况 \(\displaystyle \binom{F_{\frac{n}{2}}}{2}\)

Luogu P5900 Submission

唔-好慢

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
typedef vector <int> V;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int L=19,N=1<<L|10,P=998244353;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int I[N],J[N];
int rev[N],w[N];
void Init(){
	w[1<<(L-1)]=1;
	int t=qpow(3,(P-1)>>L);
	rep(i,(1<<(L-1))+1,1<<L) w[i]=1ll*w[i-1]*t%P;
	drep(i,(1<<(L-1))-1,1) w[i]=w[i<<1];
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
}
int Init(int n){
	int R=1,c=-1;
	while(R<=n) R<<=1,c++;
	rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	return R;
}
void NTT(int n,V &A,int f) {
	static ull a[N];
	if((int)A.size()<n) A.resize(n);
	rep(i,0,n-1) a[rev[i]]=A[i];
	for(int i=1;i<n;i<<=1) {
		int *e=w+i;
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=a[j+i]*e[j-l]%P;
				a[j+i]=a[j]+P-t;
				a[j]+=t;
			}
		}
	}
	rep(i,0,n-1) A[i]=a[i]%P,Mod2(A[i]);
	if(f==-1) {
		reverse(A.begin()+1,A.end());
		ll base=1ll*I[n]*J[n-1]%P;
		rep(i,0,n-1) A[i]=A[i]*base%P;
	}
}

V operator + (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
V operator - (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
V operator * (V a,V b) {
	int n=a.size()-1,m=b.size()-1;
	int R=Init(n+m);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
	NTT(R,a,-1),a.resize(n+m+1);
	return a;
}
V operator * (V a,const int &x) {
	for(int &i:a) i=1ll*i*x%P;
	return a;
}
V operator * (const int &x,V a) { return a*x; }

void println(const V &a){
	for(int i:a) printf("%d ",i);
	puts("");
}
V read(int n){
	V A(n);
	rep(i,0,n-1) A[i]=rd();
	return A;
}
V operator ~ (V a) {
	int n=a.size(),m=(n+1)>>1;
	if(n==1) return assert(a[0]),V{(int)qpow(a[0])};
	V b=a; b.resize(m),b=~b;
	int R=Init(n*2);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=(P+2-1ll*a[i]*b[i]%P)*b[i]%P;
	NTT(R,a,-1),a.resize(n);
	return a;
}
V Deriv(V a) {
	rep(i,0,a.size()-2) a[i]=1ll*(i+1)*a[i+1]%P;
	a.pop_back();
	return a;
}
V Integ(V a){
	a.pb(0);
	drep(i,a.size()-1,1) a[i]=1ll*a[i-1]*J[i-1]%P*I[i]%P;
	a[0]=0;
	return a;
}
V Ln(V a){
	int n=a.size();
	a=Deriv(a)*~a;
	return a.resize(n-1),Integ(a);
}
V Exp(V a) {
	if(a.size()==1) return assert(a[0]==0),V{1};
	int n=a.size();
	V b=a; b.resize((n+1)/2),b=Exp(b),b.resize(n);
	a=a-Ln(b),a[0]++;
	a=a*b,a.resize(n);
	return a;
}

V operator << (V a,int x) {
	a.resize(a.size()+x);
	drep(i,a.size()-1,x) a[i]=a[i-x];
	rep(i,0,x-1) a[i]=0;
	return a;
}
V operator >> (V a,int x) {
	if((int)a.size()<=x) return V{};
	rep(i,x,a.size()-1) a[i-x]=a[i];
	a.resize(a.size()-x);
	return a;
}

V Newton(int n){
	if(n==1) return V{0};
	if(n==2) return V{0,1};
	V G=Newton((n+1)/2); G.resize(n);
	V T=G;
	rep(i,2,n-1) {
		int t=1ll*I[i]*J[i-1]%P;
		rep(j,1,min(n/2,(n-1)/i)) T[i*j]=(T[i*j]+1ll*G[j]*t)%P;
	}
	T=Exp(T)<<1;
	V F=G-(T-G)*~(T-V{1});
	return F.resize(n),F;
}

int main(){
	int n=rd()+1; Init();
	V F=Newton(n); 
	int ans=F[--n];
	rep(i,1,(n-1)/2) ans=(ans-1ll*F[i]*F[n-i])%P;
	if(~n&1) ans=(ans-1ll*F[n/2]*(F[n/2]-1)/2)%P;
	Mod2(ans);
	printf("%d\n",ans);
}

Posted on Edited on In

有标号DAG计数

题目大意：求 \(n\) 个点有标号弱连通 \(\text{DAG}\) 数量

如果你做过类似 「CEOI2019」游乐园 这样常见的 \(\text{DAG}\) 计数问题

就会对于统计 \(\text{DAG}\) 数量的这个容斥方法十分熟悉

枚举图分层，设当前已经确定的层中点集为 \(S\) ，下一层点集为 \(T\)

\(dp_{S+T}\leftarrow dp_{S}\times 2^{|S|\cdot |T|}(-1)^{|T|+1}\)

其中 \(|S|\cdot |T|\) 为层间随意连的边数量， \((-1)^{|T|+1}\) 是针对分层不唯一的容斥

当然这样统计出的 \(\text{DAG}\) 是不连通的

那么我们先考虑用卷积来维护这样的一个图

设分层大小为 \(a_i,i\in[1,m],n=\sum a_i\) ，则上式的变化形式就是

\(\displaystyle \frac{\displaystyle n!2^{\binom{n}{2}}}{\displaystyle \prod a_i!(-1)^{a_i+1}2^{\binom{a_i}{2}}}\)

其中 \(\displaystyle \binom{n}{2}-\sum \binom{a_i}{2}\) 就能得出层间边的数量

那么令 \(\displaystyle F(x)=\sum_{n\ge 1}\frac{(-1)^{n+1}}{n!2^{\binom{n}{2}}}\) ，由于层间有序，答案是

\(\displaystyle G(x)=\sum F^i(x)=\frac{1}{1-F(x)}\)

求逆一次即可得到 \(G(x)\) ，然后补上式子中的系数 \(\displaystyle 2^{\binom{n}{2}}\)

显然不连通的 \(\text{DAG}\) 转为连通 \(\text{DAG}\) 只需要再求一次 \(\ln\) 即可

注意计算的时候是以 \(\text{EGF}\) 的形式，最后要补回阶乘

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
typedef vector <int> V;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

#ifndef ONLINE_JUDGE
#define LOG(...) fprintf(stderr,__VA_ARGS__)
#else
#define LOG(...) 
#endif

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int L=18,N=1<<L|10,P=998244353;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int I[N],J[N];
int rev[N],w[N];
void Init(){
	w[1<<(L-1)]=1;
	int t=qpow(3,(P-1)>>L);
	rep(i,(1<<(L-1))+1,1<<L) w[i]=1ll*w[i-1]*t%P;
	drep(i,(1<<(L-1))-1,1) w[i]=w[i<<1];
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
}
int Init(int n){
	int R=1,c=-1;
	while(R<=n) R<<=1,c++;
	rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	return R;
}
void NTT(int n,V &A,int f) {
	static ull a[N];
	if((int)A.size()<n) A.resize(n);
	rep(i,0,n-1) a[rev[i]]=A[i];
	for(int i=1;i<n;i<<=1) {
		int *e=w+i;
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=a[j+i]*e[j-l]%P;
				a[j+i]=a[j]+P-t;
				a[j]+=t;
			}
		}
	}
	rep(i,0,n-1) A[i]=a[i]%P,Mod2(A[i]);
	if(f==-1) {
		reverse(A.begin()+1,A.end());
		ll base=1ll*I[n]*J[n-1]%P;
		rep(i,0,n-1) A[i]=A[i]*base%P;
	}
}

V operator + (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
V operator - (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
V operator * (V a,V b) {
	int n=a.size()-1,m=b.size()-1;
	int R=Init(n+m);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
	NTT(R,a,-1),a.resize(n+m+1);
	return a;
}
void println(const V &a){
	for(int i:a) printf("%d ",i);
	puts("");
}
V read(int n){
	V A(n);
	rep(i,0,n-1) A[i]=rd();
	return A;
}
V operator ~ (V a) {
	int n=a.size(),m=(n+1)>>1;
	if(n==1) return {(int)qpow(a[0])};
	V b=a; b.resize(m),b=~b;
	int R=Init(n*2);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=(P+2-1ll*a[i]*b[i]%P)*b[i]%P;
	NTT(R,a,-1),a.resize(n);
	return a;
}
V Deriv(V a) {
	rep(i,0,a.size()-2) a[i]=1ll*(i+1)*a[i+1]%P;
	a.pop_back();
	return a;
}
V Integ(V a){
	a.pb(0);
	drep(i,a.size()-1,1) a[i]=1ll*a[i-1]*J[i-1]%P*I[i]%P;
	a[0]=0;
	return a;
}
V Ln(V a){
	int n=a.size();
	a=Deriv(a)*~a;
	return a.resize(n-1),Integ(a);
}
int Div2(int x){ return (x&1?x+P:x)/2; }
int Pow[N],IPow[N];

int main(){
	int n=rd();
	Init();
	Pow[0]=Pow[1]=IPow[0]=IPow[1]=1;
	for(int i=2,x=2,y=(P+1)/2;i<N;i++,x*=2,Mod1(x),y=Div2(y)) {
		Pow[i]=1ll*Pow[i-1]*x%P;
		IPow[i]=1ll*IPow[i-1]*y%P;
	}
	V F(n+1);
	rep(i,1,n) {
		F[i]=1ll*I[i]*IPow[i]%P;
		if(~i&1) F[i]=-F[i],Mod2(F[i]); // 这个是容斥系数 
		F[i]=P-F[i];// 这个是1-F
	}
    // 这个是1-F
	F[0]=1;
	F=~F;
	rep(i,0,n) F[i]=1ll*F[i]*Pow[i]%P;
    // 补回系数，然后做一次ln
	F=Ln(F);
	rep(i,0,n) F[i]=1ll*F[i]*J[i]%P;
	rep(i,1,n) printf("%d\n",F[i]);
}

Posted on Edited on In

有标号二分图计数

求 \(n\) 个点的有标号二分图数目

容易想到一个会重复的计算方法：暴力把图剖成两个集合，然后集合间随意连边

\(G_n=\displaystyle \sum_{i=0}^n \binom{n}{i}2^{i(n-i)}\)

而如果一个二分图包含 \(t\) 个连通块，那么在 \(G\) 中它会被计算 \(2^t\) 次

不妨设 \(\text{EGF}:\)

\(H(x)\) 为 \(n\) 个点连通的二分图的数目

\(G(x)\) 为 \(G_n\) 的生成函数

\(F(x)\) 为 \(n\) 个点二分图生成函数

容易发现 \(\displaystyle G(x)=\sum \frac{H^i(x)2^i}{i!}=\text{exp}(2H(x))\)

而我们要求的答案生成函数 \(F(x)=\text{exp}(H(x))\)

也就是说 \(F(x)=\sqrt {G(x)}\)

而根据组合意义容易发现 \(\displaystyle i(n-i)=\binom{n}{2}-\binom{i}{2}-\binom{n-i}{2}\) ，容易通过卷积得到 \(G(x)\)

然后开根即可，实际做的时候注意区分什么时候算的是 \(\text{EGF}\)

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

const int L=18,N=1<<L|10,P=998244353;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int I[N],J[N];
int rev[N],w[N];
void Init(){
	w[1<<(L-1)]=1;
	int t=qpow(3,(P-1)>>L);
	rep(i,(1<<(L-1))+1,1<<L) w[i]=1ll*w[i-1]*t%P;
	drep(i,(1<<(L-1))-1,1) w[i]=w[i<<1];
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
}
int Init(int n){
	int R=1,c=-1;
	while(R<=n) R<<=1,c++;
	rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	return R;
}
void NTT(int n,V &A,int f) {
	static ll a[N];
	if((int)A.size()<n) A.resize(n);
	rep(i,0,n-1) a[rev[i]]=A[i];
	for(int i=1;i<n;i<<=1) {
		int *e=w+i;
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=a[j+i]*e[j-l]%P;
				a[j+i]=a[j]-t;
				a[j]+=t;
			}
		}
	}
	rep(i,0,n-1) A[i]=a[i]%P,Mod2(A[i]);
	if(f==-1) {
		reverse(A.begin()+1,A.end());
		ll base=1ll*I[n]*J[n-1]%P;
		rep(i,0,n-1) A[i]=A[i]*base%P;
	}
}

V operator + (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
V operator - (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
V operator * (V a,V b) {
	int n=a.size()-1,m=b.size()-1;
	int R=Init(n+m);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
	NTT(R,a,-1),a.resize(n+m+1);
	return a;
}
void println(const V &a){
	for(int i:a) printf("%d ",i);
	puts("");
}
V read(int n){
	V A(n);
	rep(i,0,n-1) A[i]=rd();
	return A;
}
V operator ~ (V a) {
	int n=a.size(),m=(n+1)>>1;
	if(n==1) return {(int)qpow(a[0])};
	V b=a; b.resize(m),b=~b;
	int R=Init(n*2);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=(P+2-1ll*a[i]*b[i]%P)*b[i]%P;
	NTT(R,a,-1),a.resize(n);
	return a;
}

int Div2(int x){ return (x&1?x+P:x)/2; }
V Sqrt(V a){
	if(a.size()==1) return a;
	int n=a.size();
	V b=a; b.resize((n+1)/2),b=Sqrt(b),b.resize(n);
	a=a*~b; a.resize(n);
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	rep(i,0,n-1) a[i]=Div2(a[i]);
	return a;
}

int Pow[N],IPow[N];

int main(){
	int n=1e5;
	Init();
	Pow[0]=Pow[1]=IPow[0]=IPow[1]=1;
	for(int i=2,x=2,y=(P+1)/2;i<N;i++,x*=2,Mod1(x),y=Div2(y)) {
		Pow[i]=1ll*Pow[i-1]*x%P;
		IPow[i]=1ll*IPow[i-1]*y%P;
	}
	V F(n+1);
	rep(i,0,n) F[i]=1ll*I[i]*IPow[i]%P;
	F=F*F,F.resize(n+1);
	rep(i,0,n) F[i]=1ll*F[i]*Pow[i]%P;
	F=Sqrt(F);
	rep(i,1,n) printf("%d\n",int(1ll*F[i]*J[i]%P));
}

Posted on Edited on In

有标号荒漠计数

考虑随意选择一个点为根，则仙人掌的 \(\text{EGF}\) 考虑用以下方式递归生成

令树边为二元环，则一个点周围的点都是都是与它直接相连的环

断开这个点，对于周围断开的环，环上每个点下面认为是一个仙人掌，设某个环断开之后的大小为 \(c\)

当 \(c=1\) 时，不需要考虑排列重复，即为 \(F(x)\)

当 \(c>1\) 时，考虑环正反排列，即为 \(\cfrac{F^c(x)}{2}\)

那么就容易得到 \(\displaystyle F(x)=x \cdot \text{exp}(F(x)+\sum _{i\ge 2}\frac{F^i(x)}{2})\)

变一下就是 \(\displaystyle F=x\cdot \text{exp}(\frac{F^2}{2-2F}+F)=x\cdot \text{exp}(\frac{2F-F^2}{2-2F})\)

是的，我们要解这个方方方方方方程。。。牛顿迭代代代代代代代

\(\displaystyle f(F(x))=x\cdot \text{exp}(\frac{2F-F^2}{2-2F})-F=0\)

\(\displaystyle f(z)=x\cdot \text{exp}(\frac{2z-z^2}{2-2z})-z\)

\(\displaystyle f'(z)=x\cdot \text{exp}(\frac{2z-z^2}{2-2z})(1+\frac{2z-z^2}{2z^2-4z+2})-1\)

\(\displaystyle =x\cdot \text{exp}(\frac{2z-z^2}{2-2z})(\frac{1}{2}+\frac{1}{2z^2-4z+2})-1\)

设上一层的迭代结果为 \(G(x)\) ，带入牛顿迭代结论 \(\displaystyle F(x)=G(x)-\frac{f(G)}{f'(G)}\)

设 \(\displaystyle H=x\cdot \text{exp}(\frac{2G-G^2}{2-2G})\) ，那么得到Luogu题解里 \(\text{N}\color{red}\text{aCl_Fish}\) 一样的式子(还要没有推错)

\(\displaystyle F=G-\frac{2H-2G}{H(1+\frac{1}{(1-G)^2})-2}\)

最后还要变成无根，除掉 \(n\) 即可

仙人掌转荒漠您只需要一个 \(\text{exp}\) 就好了

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
const int L=18,N=1<<L|10,P=998244353;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int I[N],J[N];
int rev[N],w[N];
void Init(){
	w[1<<(L-1)]=1;
	int t=qpow(3,(P-1)>>L);
	rep(i,(1<<(L-1))+1,1<<L) w[i]=1ll*w[i-1]*t%P;
	drep(i,(1<<(L-1))-1,1) w[i]=w[i<<1];
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
}
int Init(int n){
	int R=1,c=-1;
	while(R<=n) R<<=1,c++;
	rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	return R;
}
void NTT(int n,V &A,int f) {
	static ull a[N];
	if((int)A.size()<n) A.resize(n);
	rep(i,0,n-1) a[rev[i]]=A[i];
	for(int i=1;i<n;i<<=1) {
		int *e=w+i;
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=a[j+i]*e[j-l]%P;
				a[j+i]=a[j]+P-t;
				a[j]+=t;
			}
		}
	}
	rep(i,0,n-1) A[i]=a[i]%P,Mod2(A[i]);
	if(f==-1) {
		reverse(A.begin()+1,A.end());
		ll base=1ll*I[n]*J[n-1]%P;
		rep(i,0,n-1) A[i]=A[i]*base%P;
	}
}

V operator + (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
V operator - (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
V operator * (V a,V b) {
	int n=a.size()-1,m=b.size()-1;
	int R=Init(n+m);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
	NTT(R,a,-1),a.resize(n+m+1);
	return a;
}
V operator * (V a,const int &x) {
	for(int &i:a) i=1ll*i*x%P;
	return a;
}
V operator * (const int &x,V a) { return a*x; }

void println(const V &a){
	for(int i:a) printf("%d ",i);
	puts("");
}
V read(int n){
	V A(n);
	rep(i,0,n-1) A[i]=rd();
	return A;
}
V operator ~ (V a) {
	int n=a.size(),m=(n+1)>>1;
	if(n==1) return {(int)qpow(a[0])};
	V b=a; b.resize(m),b=~b;
	int R=Init(n*2);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=(P+2-1ll*a[i]*b[i]%P)*b[i]%P;
	NTT(R,a,-1),a.resize(n);
	return a;
}
V Deriv(V a) {
	rep(i,0,a.size()-2) a[i]=1ll*(i+1)*a[i+1]%P;
	a.pop_back();
	return a;
}
V Integ(V a){
	a.pb(0);
	drep(i,a.size()-1,1) a[i]=1ll*a[i-1]*J[i-1]%P*I[i]%P;
	a[0]=0;
	return a;
}
V Ln(V a){
	int n=a.size();
	a=Deriv(a)*~a;
	return a.resize(n-1),Integ(a);
}
V Exp(V a) {
	if(a.size()==1) return assert(a[0]==0),V{1};
	int n=a.size();
	V b=a; b.resize((n+1)/2),b=Exp(b),b.resize(n);
	a=a-Ln(b),a[0]++;
	a=a*b,a.resize(n);
	return a;
}

V operator << (V a,int x) {
	a.resize(a.size()+x);
	drep(i,a.size()-1,x) a[i]=a[i-x];
	rep(i,0,x-1) a[i]=0;
	return a;
}
V operator >> (V a,int x) {
	if((int)a.size()<=x) return V{};
	rep(i,x,a.size()-1) a[i-x]=a[i];
	a.resize(a.size()-x);
	return a;
}

V Newton(int n){
	if(n==1) return V{0};
	if(n==2) return V{0,1};
	V G=Newton((n+1)/2); G.resize(n);
	V IG=~(V{1}-G);
	V H=(2*G-G*G); H.resize(n),H=H*IG*((P+1)/2),H.resize(n),H=Exp(H)<<1;
	V F=IG*IG; F.resize(n),F[0]++;
	F=H*F,F.resize(n),F[0]-=2,Mod2(F[0]);
	F=G-2*(H-G)*~F;
	return F.resize(n),F;
}

int main(){
	int n=rd()+1; Init();
	V F=Newton(n); 
	rep(i,1,F.size()-1) F[i]=1ll*F[i]*I[i]%P*J[i-1]%P;
	F=Exp(F);
	printf("%d\n",int(1ll*F.back()*J[n-1]%P));
}

Posted on Edited on In

ARC089D - ColoringBalls

题目大意

有一排 \(n\) 个球，一开始都是白色的。

然后有 \(m\) 次操作，用一个字符串表示，若第 \(i\) 个字符为r/b则表示可以选择一段区间染成 红色/蓝色。

不能直接把一个白球染成蓝色。

求最终不同的球染色情况的个数 \(\mod 10^9+7\) 。


分析

下文视 \(n,m\) 同 阶。

分析最终态，总可以描述为若干连续的红蓝段，中间由白色分开。

如果确定了每一个红蓝段的长度和交错情况，然后再在 \(n\) 个位置里分配就能得到方案数，因此可以先忽略每一段的长度来进行考虑。

对于每一个红蓝段，可以分成两类：

  1. 只出现了红色，称这样的段为单一段。

  2. 出现了蓝色，不一定出现红色，称这样的段为复合段。

    考虑这样的段如何构造得到：

    1. 先染了一次红色
    2. 然后染了一次蓝色
    3. 接下来的每一次操作，无论染红色还是蓝色，均可以使得交替次数 \(+2\) 。

    而最终得到的段，交替段的两端的红色段可以为空。

为了包含到所有情况，并且不算重，构造方案时必然需要贪心地考虑。

可以先枚举有 \(a\) 个复合段， \(b\) 个单一段。

贪心地将前 \(a+b\) 个 r 操作用以新建一个段， \(a\) 个复合段对应着前 \(a\) 个 r。

然后再为每一个复合段贪心地匹配后面的第一个 b 操作，记作 \((pos_i,match_i),i\in[1,a]\) 。

那么对于剩下的 r/b，每一个操作均可以对于 \(a\) 个中的某一些进行，称这样的r/b为自由的。

对于每一个自由的b，设其位置为 \(j\) ，其能操作的段 \((pos_i,match_i)\) 必然满足 \(pos_i<j\) 。

对于每一个自由的r，设其位置为 \(j\) ，其能操作的段 \((pos_i,match_i)\) 必然满足 \(match_i<j\) 。

对于 \(a\) 个复合段，容易求得它们各自能得到的自由操作数量，记作 \(c_i\) ，显然 \(c_i\ge c_{i+1}\) 。

设每一个段被操作了 \(b_i\) 次，满足条件的方案只需要满足 \(c_i\ge \sum_{j=i} b_j\) 。

而我们只需考虑 \(b_i\ge b_{i+1}\) 的方案，因为这样的方案更容易被满足。

其次还需要考虑这 \(a+b\) 个段之间的相对顺序：

  1. \(b\) 个单一段等价，无顺序；
  2. \(a\) 个复合段根据 \(b_i\) 分类， \(b_i\) 相同的段之间等价，需要在方案中除掉个数的阶乘。
  3. 最终还需要将 \(a,b\) 两部分归并。

考虑倒着处理 \(dp_{i,j,k}\) 表示考虑了 \([i,a]\) 这些复合段， \(b_i=j\) ， \(\sum_{l=j} b_l=k\) 。

每次枚举一个 \(b_i\) 相同的段进行转移，即 \[ dp_{i,j,k}\leftarrow \sum_{d=1} \frac{1}{d!}\sum_{l=0}^{j-1} dp_{i+d,l,k+jd} \cdot [\ \forall p\in[0,d), k-jp\leq c_{i+p}] \] 可以在 \(j\) 这一维上前缀和优化，剩余的部分转移复杂度的一个上界为 \(O(n^3\ln n)\) 。

最终还需要将 \(a,b\) 两部分归并，并且将 \(n\) 个位置分配到每一个段中。

如果最终的方案额外加入了 \(i\) 个自由操作，则每一个段可以两类。

  1. 可以为空的段：
    • 每一个复合段两端的红色段；
    • 序列两端的白色段。
  2. 不能为空的段：
    • 每一个复合段中间的段；
    • 每一个单一段；
    • 每一个交替段之间的白色段。

这是一个简单的插板问题，可以用组合数在 \(O(1)\) 时间求解。

而需要枚举 \(O(n^2)\) 个 \(a,b\) ，每次需要 \(O(n^3\ln n)\) 的 \(\text{dp}\) ，故总复杂度为 \(O(n^5\ln n)\) 。

实际上这个上界非常松，可以随意通过。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) f|=IO=='-';
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=72,INF=1e9+10,P=1e9+7;

int n,m,ans;
char s[N];
int Com[N*4][N*4],J[N],I[N];
ll qpow(ll x,ll k=P-2) {
    ll res=1;
    for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
    return res;
}
int R[N],mk[N],C[N],pos[N],c;
// R[i] 表示第i个复合段匹配的第一个b
// pos 表示每一个a出现的位置
// C[i] 表示每一个复合r之后的自由点个数
void Add(int &a,int b){
    a+=b,Mod1(a);
}
// 枚举 a 个复合段，b个单一段
void Calc(int a,int b) {
    if(!a && !b) { ans++; return; }
    rep(i,1,a) if(R[i]>m) return;
    rep(i,1,m) mk[i]=0;
    rep(i,1,a) mk[R[i]]=1;
    rep(i,1,a+1) C[i]=0;
    // 为自由的b找到能放置的第一个复合点
    rep(i,1,m) if(s[i]=='b' && !mk[i]) {
        drep(j,a,1) if(pos[j]<i) {
            C[j]++;
            break;
        }
    }
    // 为自由的r找到能放置的第一个复合点
    rep(i,a+b+1,c) {
        drep(j,a,1) if(R[j]<pos[i]) {
            C[j]++;
            break;
        }
    }
    static int dp[N][N][N];
    // dp[i][j]表示上一个放了i个，一共放了j个，处理掉分母的count[i]!
    // 每次枚举一段，且都放了k个
    dp[a+1][0][0]=1;
    drep(i,a-1,1) C[i]+=C[i+1];
    drep(i,a,1) {
        rep(j,0,C[i]) rep(k,0,C[i]) dp[i][j][k]=0;
        rep(k,1,C[i]) {
            int up=C[i];
            rep(j,i,a) {
                up=min(up-k,C[j]-k);
                if(up<0) break;
                rep(d,0,min(up,C[j+1])) Add(dp[i][k][d+k*(j-i+1)],1ll*dp[j+1][min(k-1,C[j+1])][d]*I[j-i+1]%P);
            }
        }
        dp[i][0][0]=I[a-i+1];
        rep(j,1,C[i]) rep(k,0,C[i]) Add(dp[i][j][k],dp[i][j-1][k]);
    }
    rep(i,0,C[1]) if(dp[1][C[1]][i]) {
        // 计算可以为0的段数以及不可以为0的段数
        int c1=2+a*2; // 两端的黑段，每一个非单一段两端的红段
        int c2=a+b-1+a+i*2+b; // 中间的每一个黑段，每一个非单一段除了红段以外的段，每一个单一段
        if(c2>n) continue;
        ans=(ans+1ll*Com[n+c1-1][c1+c2-1]%P*J[a]%P*Com[a+b][a]%P*dp[1][C[1]][i])%P;
    }
}

int main() {
    rep(i,0,N*4-1) rep(j,*Com[i]=1,i) Com[i][j]=Com[i-1][j]+Com[i-1][j-1],Mod1(Com[i][j]);
    rep(i,*J=1,N-1) J[i]=1ll*J[i-1]*i%P;
    I[N-1]=qpow(J[N-1]);
    drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
    n=rd(),m=rd();
    scanf("%s",s+1);
    int j=1;
    rep(i,1,m) if(s[i]=='r') {
        pos[++c]=i;
        cmax(j,i),j++;
        while(j<=m && s[j]!='b') j++;
        R[c]=j;
    }
    rep(a,0,c) rep(b,0,c-a) if((a+b)*2-1<=n) {
        Calc(a,b);
    }
    printf("%d\n",ans);
}

Posted on Edited on In

ARC114 - Paper Cutting 2

题目大意：

在一张方格图上确定了一个矩形，每次操作选择一条两行或者两列之间的线将图切开

如果切开了矩形就停止，否则将包含矩形的一部分保留

问期望多少步停止



（如果你熟练掌握概率的独立性，这道题非常简单）

称矩形内部的横竖线为关键线

考虑对于每一个横线|竖线计算其被切的概率，以矩形右边的一条竖线为例

那么在这条竖线右边的线，以及在矩形左边的线，矩形上下的横线 都与其独立

也就是说，概率就是：

这条竖线左边且在矩形右边的线和所有关键线之中，这条线是第一个被切掉的概率

那么数一下上面提到所有线的个数 \(c\) ，概率就是 \(\frac{1}{c}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const int N=2e5+10,P=998244353;

int n,m;
int I[N];
int a,b,c,d;

int main(){
	I[0]=I[1]=1;
	rep(i,2,N-1) I[i]=1ll*(P-P/i)*I[P%i]%P;
	n=rd(),m=rd();
	a=rd(),b=rd(),c=rd(),d=rd();
	if(a>c) swap(a,c);
	if(b>d) swap(b,d);
	int e=c-a+d-b,ans=1;
	rep(i,1,a-1) ans=(ans+I[a-i+e])%P;
	rep(i,c+1,n) ans=(ans+I[i-c+e])%P;
	rep(i,1,b-1) ans=(ans+I[b-i+e])%P;
	rep(i,d+1,m) ans=(ans+I[i-d+e])%P;
	printf("%d\n",ans);
}
0%