QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#867236 | #8820. Exchanging Kubic 2 | lsj2009 | TL | 55ms | 3840kb | C++98 | 3.2kb | 2025-01-23 11:48:09 | 2025-01-23 11:48:11 |
Judging History
answer
#include<bits/stdc++.h>
// #define int long long
#pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
template<int p>
struct mint {
int x;
mint() {
x=0;
}
mint(int _x) {
if(_x<0)
_x+=p;
x=_x;
}
friend mint operator + (mint a,mint b) {
return a.x+b.x>=p? a.x+b.x-p:a.x+b.x;
}
friend mint operator - (mint a,mint b) {
return a.x<b.x? a.x-b.x+p:a.x-b.x;
}
friend mint operator * (mint a,mint b) {
return 1ll*a.x*b.x%p;
}
friend mint operator ^ (mint a,ll b) {
mint res=1,base=a;
while(b) {
if(b&1)
res*=base;
base*=base; b>>=1;
}
return res;
}
friend mint operator ~ (mint a) {
return a^(p-2);
}
friend mint operator / (mint a,mint b) {
return a*(~b);
}
friend mint & operator += (mint& a,mint b) {
return a=a+b;
}
friend mint & operator -= (mint& a,mint b) {
return a=a-b;
}
friend mint & operator *= (mint& a,mint b) {
return a=a*b;
}
friend mint & operator /= (mint& a,mint b) {
return a=a/b;
}
friend mint operator ++ (mint& a) {
return a+=1;
}
friend mint operator -- (mint& a) {
return a-=1;
}
};
const int MOD=998244353;
#define mint mint<MOD>
const int N=4e2+5,M=8e2+5;
mint f[2][4][M];
bool used[N][M];
void solve() {
int n;
scanf("%d",&n);
rep(i,1,n) {
int m;
scanf("%d",&m);
while(m--) {
int x;
scanf("%d",&x);
used[i][x]=true;
}
}
mint res=0;
rep(v,-n,800-n) {
int p=0;
rep(k,0,3) {
rep(j,0,800)
f[p][k][j]=0;
}
f[p][0][0]=1;
rep(i,1,n) {
p^=1;
rep(k,0,3) {
rep(j,0,800)
f[p][k][j]=0;
}
rep(k,0,3) {
mint tot=0;
rep(j,0,800) {
tot+=f[p^1][k][j];
if(j-i>=v&&used[i][j])
f[p][k|((j-i==v)<<1)|(j-i>=v+n)][j]+=tot;
}
}
}
rep(i,0,800)
res+=mint(-v-n+1)*f[p][3][i];
}
rep(v,-1,799) {
int p=0;
rep(k,0,3) {
rep(j,0,800)
f[p][k][j]=0;
}
f[p][0][0]=1;
rep(i,1,n) {
p^=1;
rep(k,0,3) {
rep(j,0,800)
f[p][k][j]=0;
}
rep(k,0,3) {
mint tot=0;
rep(j,0,800) {
tot+=f[p^1][k][j];
if(j-i<=v&&used[i][j])
f[p][k|((j-i==v)<<1)|(j-i<=v-n)][j]+=tot;
}
}
}
rep(i,0,800)
res+=mint(v)*f[p][3][i];
}
printf("%d\n",res.x);
}
bool M2;
// g++ QOJ8820.cpp -std=c++14 -Wall -O2 -o QOJ8820
signed main() {
// file_IO();
int testcase=1;
// scanf("%d",&testcase);
while(testcase--)
solve();
debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 27ms
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: 27ms
memory: 3840kb
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: 52ms
memory: 3840kb
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: 51ms
memory: 3840kb
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: 53ms
memory: 3712kb
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: 52ms
memory: 3840kb
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: 55ms
memory: 3840kb
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: 54ms
memory: 3840kb
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: 55ms
memory: 3840kb
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: 51ms
memory: 3840kb
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: 52ms
memory: 3712kb
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: 53ms
memory: 3840kb
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: 52ms
memory: 3840kb
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: 53ms
memory: 3712kb
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: 54ms
memory: 3840kb
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: 50ms
memory: 3840kb
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: 53ms
memory: 3840kb
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: 55ms
memory: 3840kb
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: 54ms
memory: 3840kb
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: 52ms
memory: 3840kb
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: 53ms
memory: 3840kb
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: 53ms
memory: 3840kb
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...