QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #750060 | #6199. 数圈圈 | jinqihao2023 | 15 | 356ms | 10296kb | C++14 | 1.4kb | 2024-11-15 12:27:14 | 2024-11-15 12:27:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,mod=998244353;
int tid,n,x,a[N];
namespace work1
{
const int N=16,M=(1<<15)+5;
int g[N][M],h[N][M],g1[M],h1[M],f[M][N],to[N],ans[N];
void solve()
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i]>=j)to[i-1]|=(1<<j-1);
for(int i=0;i<n;i++)g[i][1<<i]=1,h[i][1<<i]=1;
for(int i=1;i<(1<<n);i++)for(int j=0;j<n;j++)if(g[j][i])
{
g1[i]=(g1[i]+g[j][i])%mod;
for(int k=0;k<n;k++)if((i>>k&1^1) && (to[j]>>k&1))g[k][i^(1<<k)]=(g[k][i^(1<<k)]+g[j][i])%mod;
}
for(int i=1;i<(1<<n);i++)for(int j=0;j<n;j++)if(h[j][i])
{
int lim=__builtin_ctz(i);if(to[j]>>lim&1)h1[i]=(h1[i]+h[j][i])%mod;
for(int k=lim;k<n;k++)if((i>>k&1^1) && (to[j]>>k&1))h[k][i^(1<<k)]=(h[k][i^(1<<k)]+h[j][i])%mod;
}
f[0][0]=1;
for(int i=1;i<(1<<n);i++)
{
int low=__builtin_ctz(i),now=i^(1<<low);
for(int j=now;;j=(j-1)&now)
{
int num=__builtin_popcount(j)+1;
for(int k=num-1;k<=n;k++)f[i][k]=(f[i][k]+1ll*f[now^j][k-num+1]*g1[j^(1<<low)])%mod;
for(int k=num;k<=n;k++)f[i][k]=(f[i][k]+1ll*f[now^j][k-num]*h1[j^(1<<low)]%mod*x)%mod;
if(!j)break;
}
}
for(int i=0;i<=n;i++)printf("%d ",f[(1<<n)-1][i]);printf("\n");
}
}
int main()
{
//freopen("story.in","r",stdin);
//freopen("story.out","w",stdout);
scanf("%d %d",&n,&x);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
if(n<=15){work1::solve();return 0;}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 1ms
memory: 7976kb
input:
1 915080344 1
output:
1 915080344
result:
ok 2 number(s): "1 915080344"
Test #2:
score: 1
Accepted
time: 0ms
memory: 7904kb
input:
1 915080344 0
output:
1 0
result:
ok 2 number(s): "1 0"
Test #3:
score: 1
Accepted
time: 0ms
memory: 9924kb
input:
8 60641044 8 8 8 8 8 8 8 8
output:
1 485128408 47996075 379627744 150492470 955348304 893852780 400745432 184663991
result:
ok 9 numbers
Test #4:
score: 1
Accepted
time: 1ms
memory: 7924kb
input:
8 5015523 0 0 0 0 0 0 0 1
output:
1 1 0 0 0 0 0 0 0
result:
ok 9 numbers
Test #5:
score: 1
Accepted
time: 0ms
memory: 7872kb
input:
6 469476507 0 0 3 4 4 4
output:
1 938953027 685386746 814057889 85780770 0 0
result:
ok 7 numbers
Test #6:
score: 1
Accepted
time: 0ms
memory: 7888kb
input:
8 430768932 0 2 2 3 4 6 6 7
output:
1 861537892 8385549 91551398 546166364 364018503 783811192 746026358 0
result:
ok 9 numbers
Test #7:
score: 1
Accepted
time: 1ms
memory: 8200kb
input:
7 861726531 0 0 6 6 6 6 6
output:
1 452173091 675192946 823218157 246524395 422107531 0 0
result:
ok 8 numbers
Subtask #2:
score: 9
Accepted
Test #8:
score: 9
Accepted
time: 330ms
memory: 9932kb
input:
15 0 1 1 1 3 6 8 10 11 11 12 13 13 14 15 15
output:
1 122 6222 173976 2941896 31329936 212468976 908747712 384836990 634979325 959428094 118389247 151372800 4147200 0 0
result:
ok 16 numbers
Test #9:
score: 9
Accepted
time: 325ms
memory: 9696kb
input:
15 0 0 0 0 0 0 0 0 0 0 0 13 14 14 14 14
output:
1 65 1563 17268 86988 158400 0 0 0 0 0 0 0 0 0 0
result:
ok 16 numbers
Test #10:
score: 9
Accepted
time: 329ms
memory: 9112kb
input:
15 0 3 7 7 7 7 7 7 7 7 10 10 10 10 10 10
output:
1 111 5069 124376 1797880 15805440 84299040 264216960 454083840 373161600 105840000 0 0 0 0 0
result:
ok 16 numbers
Test #11:
score: 9
Accepted
time: 324ms
memory: 9116kb
input:
15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 10
output:
1 11 9 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 16 numbers
Test #12:
score: 9
Accepted
time: 328ms
memory: 10012kb
input:
15 0 0 0 2 5 5 5 7 7 11 11 13 15 15 15 15
output:
1 116 5599 147353 2329717 23009526 143249418 555150240 297223999 718560223 175587487 352356480 34439040 552960 0 0
result:
ok 16 numbers
Test #13:
score: 9
Accepted
time: 0ms
memory: 7904kb
input:
1 0 1
output:
1 0
result:
ok 2 number(s): "1 0"
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 3600kb
input:
1999 534253321 3 4 6 7 7 8 8 8 9 11 12 14 14 15 16 17 18 18 19 19 19 20 22 22 26 27 28 30 31 32 34 34 35 35 35 36 37 37 38 40 42 43 44 45 47 48 50 51 52 52 52 53 54 55 55 55 57 57 58 59 61 62 64 65 65 66 66 69 69 69 69 69 71 72 72 73 73 74 76 77 79 79 81 81 82 84 85 86 86 88 92 94 95 97 97 98 99 99 ...
output:
result:
wrong answer Answer contains longer sequence [length = 2000], but output contains 0 elements
Subtask #4:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 3932kb
input:
74999 1 1 2 3 3 4 4 4 4 4 4 4 4 7 8 8 9 9 9 10 13 13 14 14 16 19 20 21 22 24 25 25 26 26 29 31 32 32 35 35 36 38 39 39 40 41 43 43 44 45 45 45 46 48 49 50 50 50 51 53 54 57 59 59 60 60 62 63 63 65 66 69 71 73 76 78 78 78 79 79 79 80 81 81 81 82 82 83 83 85 87 89 91 94 94 94 94 98 99 99 100 100 101 1...
output:
result:
wrong answer Answer contains longer sequence [length = 75000], but output contains 0 elements
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #6:
score: 5
Accepted
Test #28:
score: 5
Accepted
time: 338ms
memory: 9900kb
input:
15 0 15 15 15 13 13 13 12 10 10 9 9 6 6 4 2
output:
1 143 8673 293388 6127032 82641996 732507660 269821972 54020920 752665723 692459500 188450200 651883058 14903294 62208000 0
result:
ok 16 numbers
Test #29:
score: 5
Accepted
time: 331ms
memory: 9852kb
input:
15 0 15 15 14 11 9 9 7 7 7 6 3 3 3 2 0
output:
1 104 4455 102795 1403958 11759742 60651108 188819820 339406848 326196720 147377232 24925968 992736 2592 0 0
result:
ok 16 numbers
Test #30:
score: 5
Accepted
time: 1ms
memory: 7912kb
input:
1 0 1
output:
1 0
result:
ok 2 number(s): "1 0"
Test #31:
score: 5
Accepted
time: 329ms
memory: 9836kb
input:
15 0 3 3 2 2 1 1 0 0 0 0 0 0 0 0 0
output:
1 10 24 12 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 16 numbers
Test #32:
score: 5
Accepted
time: 356ms
memory: 10296kb
input:
15 0 15 15 15 12 9 6 6 6 6 6 6 6 6 4 3
output:
1 115 5484 141936 2193012 20978964 124871400 453572280 960513120 92542687 568572480 95256000 0 0 0 0
result:
ok 16 numbers
Subtask #7:
score: 0
Wrong Answer
Dependency #6:
100%
Accepted
Test #33:
score: 0
Wrong Answer
time: 1ms
memory: 3696kb
input:
2000 684936839 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...
output:
result:
wrong answer Answer contains longer sequence [length = 2001], but output contains 0 elements
Subtask #8:
score: 0
Wrong Answer
Test #38:
score: 0
Wrong Answer
time: 1ms
memory: 3868kb
input:
74999 604849250 72634 60382 41531 20689 20667 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1
result:
wrong answer Answer contains longer sequence [length = 75000], but output contains 1 elements
Subtask #9:
score: 0
Skipped
Dependency #6:
100%
Accepted
Dependency #7:
0%