QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750056#6199. 数圈圈jinqihao20230 1ms7976kbC++141.4kb2024-11-15 12:26:372024-11-15 12:26:38

Judging History

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

  • [2024-11-15 12:26:38]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:7976kb
  • [2024-11-15 12:26:37]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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%