Submission #3731646


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+7;
#define mo 998244353
#define ll long long
ll inv[MAXN<<2],fac[MAXN<<2],n,x[MAXN],y[MAXN],z,ans,m;
char U[MAXN],D[MAXN],L[MAXN],R[MAXN];
inline ll Cn(ll k,ll b)
{
return (ll)fac[k]*inv[b]%mo*inv[k-b]%mo;
}
inline void solve(int n,int m,char *L,char *R,char *U,char *D)
{
	ll tmp=0;
	int cl,cr,cu,cd,nowu,nowd,u,d;
	cl=cr=cu=cd=nowu=nowd=u=d=0;
	for(int i=1;i<=n;i++) cl+=L[i]-'0',cr+=R[i]-'0';
	for(int i=1;i<=m;i++) cd+=D[i]-'0',cu+=U[i]-'0';
	if(cl+cd==0){cout<<"1";exit(0);}
	tmp=1;
//	cout<<cl<<" "<<cr<<" "<<cd<<" "<<cu<<" "<<tmp<<endl;
	for(int i=1;i<=m;i++){
		nowu+=(u=U[i]-'0');nowd+=(d=D[i]-'0');
		if(u||d){
			if(u&&d) tmp=tmp*2%mo;
			if(cr!=0) ans=(ans+tmp*Cn(cr+cu+cd-nowu-nowd-1,cr-1))%mo;
			else ans+=(cu+cd-nowu-nowd==0)%mo;
			if(cl!=0) tmp=(tmp+Cn(cl+nowu+nowd-1,cl-1))%mo;
			else tmp+=(nowu+nowd==0);
//			cout<<ans<<" "<<tmp<<endl;
		}
	}
}
int main()
{
	cin>>n>>m;
	fac[0]=1;inv[1]=inv[0]=1;
	for(int i=1;i<=2*MAXN;i++) fac[i]=fac[i-1]*i%mo;
	for(int i=2;i<=2*MAXN;i++) inv[i]=(mo-mo/i)*inv[mo%i]%mo;
	for(int i=2;i<=2*MAXN;i++) inv[i]=(ll)inv[i]*inv[i-1]%mo;
//	for(int i=1;i<=n+m<<1;i++) cout<<inv[i]<<endl;
	scanf("%s%s%s%s",L+1,R+1,U+1,D+1);
	solve(n,m,L,R,U,D);
	solve(m,n,U,D,L,R);
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task E - Modern Painting
User victorique
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1343 Byte
Status WA
Exec Time 11 ms
Memory 6912 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s%s%s",L+1,R+1,U+1,D+1);
                                   ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1600
Status
AC × 7
AC × 51
WA × 34
Set Name Test Cases
Sample s01.txt, s02.txt, s03.txt, s04.txt, s05.txt, s06.txt, s07.txt
All a01.txt, a02.txt, a03.txt, a04.txt, a05.txt, a06.txt, a07.txt, a08.txt, a09.txt, a10.txt, a11.txt, a12.txt, a13.txt, a14.txt, a15.txt, a16.txt, a17.txt, a18.txt, a19.txt, a20.txt, b01.txt, b02.txt, b03.txt, b04.txt, b05.txt, b06.txt, b07.txt, b08.txt, b09.txt, b10.txt, b11.txt, b12.txt, b13.txt, b14.txt, b15.txt, b16.txt, b17.txt, b18.txt, b19.txt, b20.txt, b21.txt, b22.txt, b23.txt, b24.txt, b25.txt, b26.txt, b27.txt, b28.txt, b29.txt, b30.txt, b31.txt, b32.txt, b33.txt, b34.txt, b35.txt, b36.txt, b37.txt, b38.txt, b39.txt, b40.txt, b41.txt, b42.txt, b43.txt, b44.txt, b45.txt, b46.txt, b47.txt, b48.txt, b49.txt, b50.txt, b51.txt, b52.txt, b53.txt, b54.txt, b55.txt, b56.txt, b57.txt, b58.txt, s01.txt, s02.txt, s03.txt, s04.txt, s05.txt, s06.txt, s07.txt
Case Name Status Exec Time Memory
a01.txt WA 11 ms 6912 KB
a02.txt WA 9 ms 6784 KB
a03.txt AC 8 ms 6656 KB
a04.txt WA 11 ms 6912 KB
a05.txt WA 11 ms 6912 KB
a06.txt AC 8 ms 6656 KB
a07.txt AC 8 ms 6656 KB
a08.txt AC 8 ms 6656 KB
a09.txt AC 8 ms 6656 KB
a10.txt AC 6 ms 6528 KB
a11.txt AC 6 ms 6528 KB
a12.txt AC 6 ms 6528 KB
a13.txt AC 6 ms 6528 KB
a14.txt AC 8 ms 6656 KB
a15.txt AC 8 ms 6656 KB
a16.txt AC 6 ms 6528 KB
a17.txt WA 10 ms 6784 KB
a18.txt WA 9 ms 6784 KB
a19.txt AC 6 ms 6528 KB
a20.txt WA 10 ms 6784 KB
b01.txt WA 10 ms 6912 KB
b02.txt AC 9 ms 6784 KB
b03.txt AC 8 ms 6656 KB
b04.txt WA 10 ms 6912 KB
b05.txt WA 10 ms 6912 KB
b06.txt AC 8 ms 6656 KB
b07.txt AC 8 ms 6656 KB
b08.txt WA 7 ms 6656 KB
b09.txt AC 8 ms 6656 KB
b10.txt WA 6 ms 6528 KB
b11.txt AC 6 ms 6528 KB
b12.txt WA 6 ms 6528 KB
b13.txt WA 6 ms 6528 KB
b14.txt AC 7 ms 6656 KB
b15.txt WA 7 ms 6656 KB
b16.txt AC 6 ms 6528 KB
b17.txt AC 9 ms 6784 KB
b18.txt AC 9 ms 6784 KB
b19.txt AC 6 ms 6528 KB
b20.txt WA 10 ms 6784 KB
b21.txt AC 8 ms 6912 KB
b22.txt AC 7 ms 6912 KB
b23.txt WA 9 ms 6912 KB
b24.txt AC 7 ms 6912 KB
b25.txt WA 9 ms 6912 KB
b26.txt WA 7 ms 6912 KB
b27.txt WA 9 ms 6912 KB
b28.txt AC 8 ms 6912 KB
b29.txt WA 8 ms 6912 KB
b30.txt AC 9 ms 6912 KB
b31.txt AC 10 ms 6912 KB
b32.txt WA 8 ms 6912 KB
b33.txt WA 10 ms 6912 KB
b34.txt AC 9 ms 6912 KB
b35.txt AC 9 ms 6912 KB
b36.txt AC 7 ms 6912 KB
b37.txt AC 8 ms 6912 KB
b38.txt AC 7 ms 6912 KB
b39.txt WA 8 ms 6912 KB
b40.txt AC 7 ms 6912 KB
b41.txt WA 9 ms 6912 KB
b42.txt WA 7 ms 6912 KB
b43.txt WA 9 ms 6912 KB
b44.txt AC 8 ms 6912 KB
b45.txt WA 8 ms 6912 KB
b46.txt AC 8 ms 6912 KB
b47.txt AC 9 ms 6912 KB
b48.txt WA 8 ms 6912 KB
b49.txt WA 9 ms 6912 KB
b50.txt WA 10 ms 6912 KB
b51.txt WA 11 ms 6912 KB
b52.txt AC 7 ms 6912 KB
b53.txt WA 6 ms 6528 KB
b54.txt AC 6 ms 6528 KB
b55.txt WA 6 ms 6528 KB
b56.txt AC 6 ms 6528 KB
b57.txt AC 6 ms 6528 KB
b58.txt AC 6 ms 6528 KB
s01.txt AC 6 ms 6528 KB
s02.txt AC 6 ms 6528 KB
s03.txt AC 6 ms 6528 KB
s04.txt AC 6 ms 6528 KB
s05.txt AC 6 ms 6528 KB
s06.txt AC 6 ms 6528 KB
s07.txt AC 6 ms 6528 KB