QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111738 | #1245. Three balls | Kostlin | WA | 3ms | 3968kb | C++14 | 2.4kb | 2023-06-08 10:51:20 | 2023-06-08 10:51:25 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define fi first
#define sc second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int N=10005,oo=1e9,mod=998244353;
inline int read() {
int x=0,flag=0;char ch=getchar();
while(ch<'0'||ch>'9') {flag|=(ch=='-');ch=getchar();}
while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return flag?-x:x;
}
inline int mx(int x,int y) {return x>y?x:y;}
inline int mn(int x,int y) {return x<y?x:y;}
inline void swp(int &x,int &y) {x^=y^=x^=y;}
inline int as(int x) {return x>0?x:-x;}
int n,r1,r2,r3,A,B,C,D,Cs[N][N],Sm[N][N],psum[N];
char s1[N],s2[N],s3[N];
#define S(i,j) Sm[(j)+D][i]
inline int calc(int n,int m) {
if(n<m||m<0) return 0;
else return Cs[n][m];
}
int main() {
n=read();
r1=read(); scanf("%s",s1+1);
r2=read(); scanf("%s",s2+1);
r3=read(); scanf("%s",s3+1);
for(int i=1;i<=n;++i) {
int F=(s1[i]=='1')+(s2[i]=='1')*2+(s3[i]=='1')*4;
switch(F) {
case 0:++A;break;
case 1:++B;break;
case 2:++C;break;
case 3:++D;break;
case 4:++D;break;
case 5:++C;break;
case 6:++B;break;
case 7:++A;break;
}
}
Cs[0][0]=Sm[0][0]=1;
for(int i=1;i<=n;++i) {
Cs[i][0]=Cs[i][i]=1;
for(int j=1;j<i;++j) Cs[i][j]=(Cs[i-1][j-1]+Cs[i-1][j])%mod;
}
S(0,-D)=0;
for(int i=0;i<=A;++i)
for(int j=0;j<=D;++j)
S(0,-D)=(S(0,-D)+1ll*Cs[A][i]*Cs[D][j])%mod;
for(int a=1;a<=A+D;++a) {
S(a,-D)=S(a-1,-D);
for(int i=0;i<=A;++i)
if(a-i>0)
S(a,-D)=(S(a,-D)-1ll*calc(A,i)*calc(D,a-i-1)%mod+mod)%mod;
}
for(int d=-D;d<A;++d) {
for(int i=A+D;i>=0;--i)
psum[i]=(psum[i+1]+1ll*calc(A,i)*calc(D,i-d))%mod;
for(int a=0,lim;a<=A+D;++a) {
lim=(a+d)/2;
if((a+d)%2==1) ++lim;
S(a,d+1)=(S(a,d)-psum[mx(lim,0)]+mod)%mod;
}
}
int ans=0,pnow=1,lim1,lim2;
for(int i=0;i<=B;++i)
for(int j=0;j<=C;++j) {
lim1=r3-(i+j);lim2=mx(r1-(B-i+j),r2-(i+C-j))-D;
ans=(ans+1ll*Cs[B][i]*Cs[C][j]%mod*S(mx(lim1+1,0),mx(lim2+1,-D)))%mod;
}
for(int i=1;i<=n;++i) pnow=2ll*pnow%mod;
ans=(pnow-ans+mod)%mod;
printf("%d\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
3 1 000 1 100 0 111
output:
7
result:
ok answer is '7'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
5 2 10110 0 11010 1 00000
output:
19
result:
ok answer is '19'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
3 2 011 0 100 3 010
output:
8
result:
ok answer is '8'
Test #4:
score: 0
Accepted
time: 3ms
memory: 3836kb
input:
5 1 11010 3 00001 4 01011
output:
32
result:
ok answer is '32'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
1 1 1 1 1 1 0
output:
2
result:
ok answer is '2'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
1 1 0 0 1 1 0
output:
2
result:
ok answer is '2'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
10 4 0001001011 6 0000011100 4 1011000101
output:
969
result:
ok answer is '969'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
15 4 110001100010010 11 101101011011001 0 001110001001110
output:
32227
result:
ok answer is '32227'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
15 9 011001010111000 7 101000010111010 9 010000110010010
output:
31656
result:
ok answer is '31656'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
15 15 011010001011011 6 101000010001001 6 000010111110010
output:
32768
result:
ok answer is '32768'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
15 0 100010010001000 0 011100000001011 0 100000100111111
output:
3
result:
ok answer is '3'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
14 0 11101010011000 0 11101010011000 0 11101010011000
output:
1
result:
ok answer is '1'
Test #13:
score: -100
Wrong Answer
time: 1ms
memory: 3900kb
input:
37 28 1001101111100111110011111100101110110 32 1001011110011111110100111110100110010 21 1001000111000000110011000001100011111
output:
679477111
result:
wrong answer expected '438952513', found '679477111'