QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#67462#2579. 开关alpha1022100 ✓105ms79660kbC++141.5kb2022-12-10 16:11:422022-12-10 16:11:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-10 16:11:43]
  • 评测
  • 测评结果:100
  • 用时:105ms
  • 内存:79660kb
  • [2022-12-10 16:11:42]
  • 提交

answer

#include <cstdio>
using namespace std;
const int N = 100;
const int S = 5e4;
const int mod = 998244353;
const int inv = 499122177;
int n,s[N + 5],p[N + 5],sum,isum,ans;
int fr[N + 5][(S << 1) + 5],gr[N + 5][(S << 1) + 5];
int *f[N + 5],*g[N + 5];
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",s + i),s[i] = s[i] ? mod - 1 : 1;
    for(register int i = 1;i <= n;++i)
        scanf("%d",p + i),sum += p[i];
    for(register int i = 0;i <= n;++i)
        f[i] = fr[i] + S,g[i] = gr[i] + S;
    f[0][0] = g[0][0] = 1;
    for(register int i = 1;i <= n;++i)
        for(register int j = -sum;j <= sum;++j)
            j + p[i] <= sum && (f[i][j + p[i]] = (f[i][j + p[i]] + (long long)f[i - 1][j] * inv) % mod,g[i][j + p[i]] = (g[i][j + p[i]] + (long long)g[i - 1][j] * inv) % mod),
            j - p[i] >= -sum && (f[i][j - p[i]] = (f[i][j - p[i]] + (long long)s[i] * f[i - 1][j] % mod * inv) % mod,g[i][j - p[i]] = (g[i][j - p[i]] + (long long)g[i - 1][j] * inv) % mod);
    isum = fpow(sum,mod - 2);
    for(register int i = -sum;i < sum;++i)
        ans = (ans + ((long long)f[n][i] * g[n][sum] % mod - (long long)f[n][sum] * g[n][i] % mod + mod) * sum % mod * fpow((i - sum + mod) % mod,mod - 2)) % mod;
    ans = (long long)ans * fpow(g[n][sum],mod - 3) % mod;
    printf("%d\n",ans);
}

详细

Test #1:

score: 10
Accepted
time: 14ms
memory: 3144kb

input:

2
1 1
23723 26273

output:

877668810

result:

ok single line: '877668810'

Test #2:

score: 10
Accepted
time: 18ms
memory: 3204kb

input:

2
1 0
18216 31771

output:

489970511

result:

ok single line: '489970511'

Test #3:

score: 10
Accepted
time: 11ms
memory: 7848kb

input:

8
1 1 0 1 1 0 1 0
1270 10205 3901 3809 8931 2530 11580 7773

output:

193550909

result:

ok single line: '193550909'

Test #4:

score: 10
Accepted
time: 27ms
memory: 7796kb

input:

8
0 1 0 0 0 1 0 0
5929 4817 1939 5783 7039 5771 9785 8934

output:

662840715

result:

ok single line: '662840715'

Test #5:

score: 10
Accepted
time: 1ms
memory: 2520kb

input:

100
0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

186395599

result:

ok single line: '186395599'

Test #6:

score: 10
Accepted
time: 3ms
memory: 2628kb

input:

100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 2 2 1 2 1 1 2 1 2 1 2 1 2 1 2 2 1 1 1 1 1 2 2 2 2 2 1 2 1 1 1 2 1 1 1 2 2 1 2 2 1 2 ...

output:

507890478

result:

ok single line: '507890478'

Test #7:

score: 10
Accepted
time: 2ms
memory: 2548kb

input:

100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 1 2 2 1 2 1 2 2 2 1 1 2 1 1 1 2 1 2 1 1 1 1 2 2 1 1 2 1 2 2 2 1 1 2 2 1 1 2 1 2 1 2 2 1 1 ...

output:

133411468

result:

ok single line: '133411468'

Test #8:

score: 10
Accepted
time: 4ms
memory: 5460kb

input:

100
0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0
24 28 18 19 22 36 35 24 7 19 26 2 31 20 33 11 20 37 11 36 9 28 16 20 46 28 5 20 40 27 13 15 28 7...

output:

988115696

result:

ok single line: '988115696'

Test #9:

score: 10
Accepted
time: 1ms
memory: 5448kb

input:

100
1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 1 0 1 0
21 11 16 21 30 35 10 3 15 33 39 7 16 31 24 27 4 15 38 16 6 7 18 11 8 31 8 17 12 20 27 9 44 9 31 ...

output:

124960105

result:

ok single line: '124960105'

Test #10:

score: 10
Accepted
time: 105ms
memory: 79660kb

input:

100
1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1
840 587 741 540 310 84 284 345 368 251 545 676 754 274 266 97 858 486 108 727 373 283 722 539 29...

output:

114906083

result:

ok single line: '114906083'

Extra Test:

score: 0
Extra Test Passed