【组合】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;
}