【组合】Modern Painting

组合问题

传送门：Code Festival 2017 qual A E

果然是现代艺术

思路：

  • 考虑第一个走的人是上下方向的，那么显然这个人会把平面分成两块；
  • 如果有两个人处于不同列且都是从上往下走的，那么显然这两个人中间的几列是唯一的；
  • 所以结果一定是中间若干列把平面分成左右两半；
  • 考虑左半边，记上下总共$x$人，左边有$y$人，则方案数为$\binom{x+y}{y}-\binom{x+y-1}{y}=\binom{x+y-1}{y-1}$，可以理解为先后有$x+y$个人要走，其中第一个走的必须为左边的人；也可以利用平面坐标系+翻折得到；
  • 右半边同理；
  • 这样可以求出左边$f_i,g_i$表示第$i$列左边和右边的方案数；
  • 然后答案为$\sum f_{l-1}\times g_{r+1}\times2^{cnt(l,r)}$，其中$cnt(l,r)$为$[l,r]$中有多少列上下都有人；
  • 把这个式子化作只关于$l,r$的式子即可；

注意：

  • 全0要特判；
  • 组合数时注意两边没人的情况。

代码如下：

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
#include<bits/stdc++.h>
using namespace std;
#define N 420000
#define LL long long
const LL mod=998244353;
LL n,m,ans,pw[N],f[N],g[N],fac[N],ifac[N];
char a[N],b[N],c[N],d[N];
bool chk;
LL inv(LL x){return x==1?1:(mod-mod/x)*inv(mod%x)%mod;}
LL C(LL x,LL y){if (y<0){if (x<0) return 1; return 0;} return fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
void solve(LL n,LL m,char a[],char b[],char c[],char d[]){
	memset(f,0,sizeof f); memset(g,0,sizeof g);
	LL l=0,r=0,sum=0,sum2=0,cnt=0,cnt2=0,tmp=0;
	for (LL i=1;i<=m;i++){
		if (c[i]=='1') l++;
		if (d[i]=='1') r++;
	}
	for (LL i=1;i<=n;i++){
		if (a[i]=='1') sum++;
		if (b[i]=='1') sum++;
		if (a[i]=='1' && b[i]=='1') sum2++;
	}
	if (a[1]=='1'||b[1]=='1') f[0]=1;
	if (a[n]=='1'||b[n]=='1') tmp=g[n+1]=pw[sum2];
	for (LL i=1;i<=n;i++){
		if (i>1&&(a[i-1]=='1'||b[i-1]=='1')) g[i]=C(sum-cnt+r-1,r-1)*pw[cnt2]%mod;
		tmp=(tmp+g[i])%mod;
		if (a[i]=='1') cnt++;
		if (b[i]=='1') cnt++;
		if (a[i]=='1' && b[i]=='1') cnt2++;
		if (i<n&&(a[i+1]=='1'||b[i+1]=='1')) f[i]=C(cnt+l-1,l-1)*inv(pw[cnt2])%mod;
	}
	for (LL i=1;i<=n;i++){
		tmp=(tmp-g[i]+mod)%mod;
		ans=(ans+f[i-1]*tmp)%mod;
	}
}
int main(){
	scanf("%lld%lld",&n,&m);
	scanf("%s%s%s%s",a+1,b+1,c+1,d+1);
	for (int i=1;i<=n;i++) chk|=(a[i]=='1')|(b[i]=='1');
	for (int i=1;i<=m;i++) chk|=(c[i]=='1')|(d[i]=='1');
	if (!chk){puts("1"); return 0;}
	pw[0]=1; for (LL i=1;i<N;i++) pw[i]=pw[i-1]*2%mod;
	fac[0]=1; for (LL i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
	ifac[N-1]=inv(fac[N-1]); for (LL i=N-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
	solve(n,m,a,b,c,d);
	solve(m,n,c,d,a,b);
	printf("%lld\n",ans);
	
	return 0;
}