QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111738#1245. Three ballsKostlinWA 3ms3968kbC++142.4kb2023-06-08 10:51:202023-06-08 10:51:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-08 10:51:25]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3968kb
  • [2023-06-08 10:51:20]
  • 提交

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'