QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750056 | #6199. 数圈圈 | jinqihao2023 | 0 | 1ms | 7976kb | C++14 | 1.4kb | 2024-11-15 12:26:37 | 2024-11-15 12:26:38 |
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 %d",&tid,&n,&x);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
if(n<=15){work1::solve();return 0;}
return 0;
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
1 915080344 1
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 3812kb
input:
15 0 1 1 1 3 6 8 10 11 11 12 13 13 14 15 15
output:
1
result:
wrong answer Answer contains longer sequence [length = 16], but output contains 1 elements
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 7976kb
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:
1 1
result:
wrong answer 2nd numbers differ - expected: '807105292', found: '1'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 0ms
memory: 3820kb
input:
15 0 15 15 15 13 13 13 12 10 10 9 9 6 6 4 2
output:
1
result:
wrong answer Answer contains longer sequence [length = 16], but output contains 1 elements
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Wrong Answer
Test #38:
score: 0
Wrong Answer
time: 1ms
memory: 4100kb
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:
0%