QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#866923#8820. Exchanging Kubic 2HanghangTL 138ms3712kbC++201.2kb2025-01-22 21:54:182025-01-22 21:54:19

Judging History

This is the latest submission verdict.

  • [2025-01-22 21:54:19]
  • Judged
  • Verdict: TL
  • Time: 138ms
  • Memory: 3712kb
  • [2025-01-22 21:54:18]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=403,H=998244353;
ll n,ans,f[N*2][2][2],g[N*2][2][2];
vector<int>S[N];
void Add(ll &x,ll y){x=(x+y)%H;}
ll Sol1(ll v)
{
	memset(f,0,sizeof(f));f[0][0][0]=1;ll s=0;
	for(int t=1;t<=n;t++)
	{
		memcpy(g,f,sizeof(g));memset(f,0,sizeof(f));
		for(int i=1;i<2*N;i++)for(int x:{0,1})for(int y:{0,1})
			Add(g[i][x][y],g[i-1][x][y]);
		for(int z:S[t])if(z-t<=v)for(int x:{0,1})for(int y:{0,1})
			Add(f[z][x|(z-t==v)][y|(z-t<=v-n)],g[z][x][y]);
	}
	for(int i=0;i<2*N;i++)Add(s,f[i][1][1]);
	return s;
}
ll Sol2(ll v)
{
	memset(f,0,sizeof(f));f[0][0][0]=1;ll s=0;
	for(int t=1;t<=n;t++)
	{
		memcpy(g,f,sizeof(g));memset(f,0,sizeof(f));
		for(int i=1;i<2*N;i++)for(int x:{0,1})for(int y:{0,1})
			Add(g[i][x][y],g[i-1][x][y]);
		for(int z:S[t])if(z-t>=v)for(int x:{0,1})for(int y:{0,1})
			Add(f[z][x|(z-t==v)][y|(z-t>=v+n)],g[z][x][y]);
	}
	for(int i=0;i<2*N;i++)Add(s,f[i][1][1]);
	return s;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int len;cin>>len;S[i].resize(len);
		for(auto &x:S[i])cin>>x;
	}
	for(ll v=-400;v<=800;v++)Add(ans,Sol1(v)*(v+H)); 
	for(ll v=-400;v<=800;v++)Add(ans,Sol2(v)*(-v-n+1+H));
	cout<<ans;
}

详细

Test #1:

score: 100
Accepted
time: 71ms
memory: 3712kb

input:

5
3 1 2 3
1 2
0
4 0 2 3 4
2 2 3

output:

0

result:

ok "0"

Test #2:

score: 0
Accepted
time: 72ms
memory: 3712kb

input:

5
4 1 2 3 7
4 5 7 8 9
4 2 3 6 9
5 0 1 4 7 9
8 0 1 2 3 6 7 8 9

output:

16

result:

ok "16"

Test #3:

score: 0
Accepted
time: 135ms
memory: 3712kb

input:

10
8 1 2 3 7 15 17 18 19
11 1 2 5 8 9 10 13 16 18 19 20
12 0 1 4 5 6 7 8 9 11 16 17 19
12 0 1 3 5 9 10 11 15 16 17 18 19
6 2 8 11 15 18 19
11 0 4 6 7 8 10 11 13 16 18 19
13 1 3 4 6 8 9 10 12 13 14 15 19 20
13 2 4 5 8 9 10 11 13 14 15 16 17 20
10 2 3 5 6 8 10 13 14 18 19
12 2 3 4 5 8 9 12 13 15 16 19...

output:

27895

result:

ok "27895"

Test #4:

score: 0
Accepted
time: 135ms
memory: 3584kb

input:

10
12 0 3 4 5 6 7 8 13 14 17 19 20
15 0 1 2 4 5 6 8 9 11 12 13 14 15 18 19
9 2 7 8 9 13 15 16 18 19
17 0 1 2 3 4 5 6 7 8 9 10 11 15 16 17 18 19
17 0 1 2 4 6 7 8 9 10 11 12 14 15 16 17 19 20
17 0 1 2 3 6 8 10 11 12 13 14 15 16 17 18 19 20
15 1 3 4 6 7 9 10 11 12 13 14 15 17 19 20
16 0 1 2 3 5 6 8 9 1...

output:

625955

result:

ok "625955"

Test #5:

score: 0
Accepted
time: 135ms
memory: 3456kb

input:

10
11 0 2 3 4 6 7 8 9 10 18 19
18 1 2 3 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20
17 0 1 2 3 5 6 7 8 9 10 11 13 14 15 16 18 20
18 0 1 2 3 4 5 6 8 9 10 11 12 13 16 17 18 19 20
16 0 1 2 4 5 6 7 8 9 10 11 12 13 14 17 20
20 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
15 0 1 2 3 4 7 9 10 11 14 15 16...

output:

792393

result:

ok "792393"

Test #6:

score: 0
Accepted
time: 137ms
memory: 3712kb

input:

10
18 0 1 2 4 5 6 7 8 9 10 12 13 15 16 17 18 19 20
15 2 3 4 5 6 8 9 10 12 13 14 16 17 18 19
15 0 2 3 4 5 7 10 13 14 15 16 17 18 19 20
17 0 1 2 6 7 8 9 11 12 13 14 15 16 17 18 19 20
17 0 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20
17 0 3 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
16 0 1 2 3 4 5 6 7 10 12 ...

output:

360237

result:

ok "360237"

Test #7:

score: 0
Accepted
time: 137ms
memory: 3712kb

input:

10
18 0 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19
18 0 1 2 3 4 6 7 9 10 11 13 14 15 16 17 18 19 20
15 0 2 4 5 6 7 9 11 12 13 14 16 17 19 20
18 0 1 2 3 4 6 7 8 10 11 12 13 14 15 17 18 19 20
17 0 1 2 3 5 6 7 8 10 11 12 13 14 15 16 17 18
18 0 2 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20
17 0 1 2 3 5 ...

output:

5546330

result:

ok "5546330"

Test #8:

score: 0
Accepted
time: 137ms
memory: 3712kb

input:

10
17 0 1 2 3 4 7 9 10 12 13 14 15 16 17 18 19 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20
19 0 1 2 3 4 5 6 7 8 9 12 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
19 0 1 2 3 4 5 6 7 8 9 11 12 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

output:

8298325

result:

ok "8298325"

Test #9:

score: 0
Accepted
time: 135ms
memory: 3712kb

input:

10
17 1 2 3 4 5 6 7 8 9 10 11 12 15 16 18 19 20
19 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 18 19 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
18 0 1 2 3 4 6 8 9 10 11 12 13 14 15 16...

output:

8321362

result:

ok "8321362"

Test #10:

score: 0
Accepted
time: 135ms
memory: 3712kb

input:

10
19 0 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20
18 0 1 2 3 4 5 6 7 9 10 11 12 13 14 15 17 18 20
19 0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 19 20
19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20
18 0 1 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20
20 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 ...

output:

14615813

result:

ok "14615813"

Test #11:

score: 0
Accepted
time: 136ms
memory: 3584kb

input:

10
17 1 2 3 4 6 7 8 10 11 12 13 14 15 17 18 19 20
20 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
19 0 1 2 3 4 5 6 7 8 9 10 11 12 14 16 17 18 19 20
19 0 1 2 3 4 5 6 7 8 9 11 12 13 15 16 17 18 19 20
19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20
17 0 2 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19
...

output:

6260430

result:

ok "6260430"

Test #12:

score: 0
Accepted
time: 134ms
memory: 3712kb

input:

10
18 0 1 3 4 5 6 7 8 9 10 12 13 14 15 16 17 19 20
19 0 1 2 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20
18 0 1 2 3 4 5 6 7 8 9 10 11 12 14 16 17 18 20
18 0 1 2 3 4 6 7 8 9 11 12 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...

output:

14649479

result:

ok "14649479"

Test #13:

score: 0
Accepted
time: 135ms
memory: 3584kb

input:

10
18 0 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20
19 0 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 19 20
19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20
18 0 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 19 20
16 1 2 6 7 8 9 10 11 12 13 14 15 16 18 19 20
19 0 1 2 3 4 6 8 9 10 11 12 13 14 15 16 17 18 19 20
19 ...

output:

11884364

result:

ok "11884364"

Test #14:

score: 0
Accepted
time: 136ms
memory: 3456kb

input:

10
18 0 1 2 3 4 5 6 7 9 10 12 13 15 16 17 18 19 20
20 0 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20
19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
20 0 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
19 0 1 2 3 4 5 6 7 8 10 11 12 13 15 16 17 18 19 20
16 0 3 4 5 6 8 9 10 11 12 15 16 17 18 1...

output:

12608630

result:

ok "12608630"

Test #15:

score: 0
Accepted
time: 137ms
memory: 3712kb

input:

10
20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
19 0 1 2 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20
17 0 1 2 3 4 5 7 9 10 11 12 15 16 17 18 19 20
20 0 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20
19 0 1 2 3 4 5 6 7 8 9 10 12 13 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

output:

15597786

result:

ok "15597786"

Test #16:

score: 0
Accepted
time: 137ms
memory: 3456kb

input:

10
20 0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
18 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
19 0 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12...

output:

18162391

result:

ok "18162391"

Test #17:

score: 0
Accepted
time: 136ms
memory: 3456kb

input:

10
19 0 1 2 3 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20
18 1 2 3 4 5 6 7 8 9 10 11 12 14 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20
18 0 1 2 3 5 6 7 8 9 11 12 13 14 16 17 18 19 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 ...

output:

13636845

result:

ok "13636845"

Test #18:

score: 0
Accepted
time: 138ms
memory: 3712kb

input:

10
19 0 1 2 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 0 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20
19 0 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20
18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14...

output:

23060640

result:

ok "23060640"

Test #19:

score: 0
Accepted
time: 137ms
memory: 3584kb

input:

10
19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 20
18 0 1 2 3 5 6 8 9 10 11 12 13 14 15 16 17 19 20
19 0 1 2 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
18 0 1 2 4 5 6 8 9 10 11 12 13 14 15 16 17 19 20
20 0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 1...

output:

16391978

result:

ok "16391978"

Test #20:

score: 0
Accepted
time: 137ms
memory: 3712kb

input:

10
19 0 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 19 20
20 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
19 0 1 2 3 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20
19 1 2 3 4 6 7 8 9 10 11 12 13 14...

output:

17643155

result:

ok "17643155"

Test #21:

score: 0
Accepted
time: 136ms
memory: 3712kb

input:

10
19 0 1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
19 0 1 2 3 4 5 6 7 8 9 10 11 12...

output:

22529158

result:

ok "22529158"

Test #22:

score: 0
Accepted
time: 136ms
memory: 3712kb

input:

10
19 0 1 2 3 4 5 6 7 9 10 11 12 13 14 16 17 18 19 20
19 0 1 2 3 4 5 6 7 8 10 11 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
19 0 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20
20 0 1 2 3 4 5 6 7 8 9 10 11 12 ...

output:

23343575

result:

ok "23343575"

Test #23:

score: -100
Time Limit Exceeded

input:

400
398 1 2 3 7 15 17 18 19 22 23 26 29 30 31 34 37 39 40 41 42 43 46 47 48 49 50 51 53 58 59 61 63 64 66 68 72 73 74 78 79 80 81 82 86 92 95 99 102 103 105 109 111 112 113 115 116 118 121 123 124 127 129 130 132 134 135 136 138 139 140 141 145 146 149 151 152 155 156 157 158 160 161 162 163 164 167...

output:


result: