Submission #3731779
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,m,ans; 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; ll 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+cr+cu==0){cout<<"1";exit(0);} tmp=1; 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=(ans+tmp*(cu+cd-nowu-nowd==0))%mo; if(cl!=0) tmp=(tmp+Cn(cl+nowu+nowd-1,cl-1))%mo; else tmp=(tmp+(nowu+nowd==0))%mo; } } } int main() { cin>>n>>m; fac[0]=1;inv[1]=inv[0]=1; for(int i=1;i<=4*MAXN-10;i++) fac[i]=fac[i-1]*i%mo; for(int i=2;i<=4*MAXN-10;i++) inv[i]=(mo-mo/i)*inv[mo%i]%mo; for(int i=2;i<=4*MAXN-10;i++) inv[i]=(ll)inv[i]*inv[i-1]%mo; 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 | 1600 |
Code Size | 1206 Byte |
Status | AC |
Exec Time | 15 ms |
Memory | 6912 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:36: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 | 1600 / 1600 | ||||
Status |
|
|
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 | AC | 15 ms | 6912 KB |
a02.txt | AC | 13 ms | 6784 KB |
a03.txt | AC | 12 ms | 6656 KB |
a04.txt | AC | 15 ms | 6912 KB |
a05.txt | AC | 15 ms | 6912 KB |
a06.txt | AC | 12 ms | 6656 KB |
a07.txt | AC | 12 ms | 6656 KB |
a08.txt | AC | 12 ms | 6656 KB |
a09.txt | AC | 12 ms | 6656 KB |
a10.txt | AC | 10 ms | 6528 KB |
a11.txt | AC | 10 ms | 6528 KB |
a12.txt | AC | 10 ms | 6528 KB |
a13.txt | AC | 10 ms | 6528 KB |
a14.txt | AC | 12 ms | 6656 KB |
a15.txt | AC | 12 ms | 6656 KB |
a16.txt | AC | 10 ms | 6528 KB |
a17.txt | AC | 14 ms | 6912 KB |
a18.txt | AC | 13 ms | 6784 KB |
a19.txt | AC | 10 ms | 6528 KB |
a20.txt | AC | 14 ms | 6784 KB |
b01.txt | AC | 15 ms | 6912 KB |
b02.txt | AC | 13 ms | 6784 KB |
b03.txt | AC | 12 ms | 6656 KB |
b04.txt | AC | 14 ms | 6912 KB |
b05.txt | AC | 15 ms | 6912 KB |
b06.txt | AC | 12 ms | 6656 KB |
b07.txt | AC | 12 ms | 6656 KB |
b08.txt | AC | 12 ms | 6656 KB |
b09.txt | AC | 12 ms | 6656 KB |
b10.txt | AC | 10 ms | 6528 KB |
b11.txt | AC | 10 ms | 6528 KB |
b12.txt | AC | 10 ms | 6528 KB |
b13.txt | AC | 10 ms | 6528 KB |
b14.txt | AC | 11 ms | 6656 KB |
b15.txt | AC | 12 ms | 6656 KB |
b16.txt | AC | 10 ms | 6528 KB |
b17.txt | AC | 13 ms | 6912 KB |
b18.txt | AC | 13 ms | 6784 KB |
b19.txt | AC | 10 ms | 6528 KB |
b20.txt | AC | 14 ms | 6784 KB |
b21.txt | AC | 12 ms | 6912 KB |
b22.txt | AC | 12 ms | 6912 KB |
b23.txt | AC | 13 ms | 6912 KB |
b24.txt | AC | 12 ms | 6912 KB |
b25.txt | AC | 14 ms | 6912 KB |
b26.txt | AC | 13 ms | 6912 KB |
b27.txt | AC | 13 ms | 6912 KB |
b28.txt | AC | 12 ms | 6912 KB |
b29.txt | AC | 13 ms | 6912 KB |
b30.txt | AC | 13 ms | 6912 KB |
b31.txt | AC | 14 ms | 6912 KB |
b32.txt | AC | 12 ms | 6912 KB |
b33.txt | AC | 14 ms | 6912 KB |
b34.txt | AC | 13 ms | 6912 KB |
b35.txt | AC | 14 ms | 6912 KB |
b36.txt | AC | 11 ms | 6912 KB |
b37.txt | AC | 12 ms | 6912 KB |
b38.txt | AC | 12 ms | 6912 KB |
b39.txt | AC | 12 ms | 6912 KB |
b40.txt | AC | 13 ms | 6912 KB |
b41.txt | AC | 14 ms | 6912 KB |
b42.txt | AC | 13 ms | 6912 KB |
b43.txt | AC | 13 ms | 6912 KB |
b44.txt | AC | 12 ms | 6912 KB |
b45.txt | AC | 13 ms | 6912 KB |
b46.txt | AC | 13 ms | 6912 KB |
b47.txt | AC | 13 ms | 6912 KB |
b48.txt | AC | 12 ms | 6912 KB |
b49.txt | AC | 13 ms | 6912 KB |
b50.txt | AC | 14 ms | 6912 KB |
b51.txt | AC | 15 ms | 6912 KB |
b52.txt | AC | 11 ms | 6912 KB |
b53.txt | AC | 10 ms | 6528 KB |
b54.txt | AC | 10 ms | 6528 KB |
b55.txt | AC | 10 ms | 6528 KB |
b56.txt | AC | 10 ms | 6528 KB |
b57.txt | AC | 10 ms | 6528 KB |
b58.txt | AC | 10 ms | 6528 KB |
s01.txt | AC | 10 ms | 6528 KB |
s02.txt | AC | 10 ms | 6528 KB |
s03.txt | AC | 10 ms | 6528 KB |
s04.txt | AC | 10 ms | 6528 KB |
s05.txt | AC | 10 ms | 6528 KB |
s06.txt | AC | 10 ms | 6528 KB |
s07.txt | AC | 10 ms | 6528 KB |