QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#67462 | #2579. 开关 | alpha1022 | 100 ✓ | 105ms | 79660kb | C++14 | 1.5kb | 2022-12-10 16:11:42 | 2022-12-10 16:11:43 |
Judging History
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