QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#454630 | #8820. Exchanging Kubic 2 | 275307894a | WA | 839ms | 16704kb | C++14 | 2.0kb | 2024-06-25 07:19:53 | 2024-06-25 07:19:54 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=800+5,M=N*4+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int n,m,vis[N][N],k=800;
ll dp[N][N][2],f[N][N][2];
void add(ll &x,ll y){(x+=y)>=mod&&(x-=mod);}
void Solve(){
int i,j;scanf("%d",&n);
for(i=1;i<=n;i++){
int len,x;scanf("%d",&len);
while(len--) scanf("%d",&x),vis[i][x]=1;
}
for(i=0;i<=k;i++) if(vis[1][i]) dp[i][1][0]=1;
for(i=2;i<=n;i++){
for(j=0;j<=k;j++) for(int h=0;h<=k;h++) for(int o:{0,1}) add(dp[j+1][h+1][o],dp[j][h][o]);
for(j=0;j<=k;j++) if(!vis[i][j]) Me(dp[j],0);
for(j=0;j<=k;j++) for(int h=0;h<=k;h++){
if(h<i){
for(int o:{0,1}) add(dp[j][i][o],dp[j][h][o]),dp[j][h][o]=0;
}
if(h>n+i-1){
// if(dp[j][h][0]) gdb(dp[j][h][0],i,h,n-i+1);
add(dp[j][n+i-1][1],dp[j][h][0]*(h-(n+i-1))%mod);
for(int o:{0,1}) add(dp[j][n+i-1][o],dp[j][h][o]),dp[j][h][o]=0;
}
}
}
ll ans=0;
for(i=0;i<=k;i++) for(j=0;j<=k;j++) ans+=dp[i][j][1];
printf("%lld\n",(ans%mod+mod)%mod);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 14ms
memory: 16280kb
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: 17ms
memory: 16264kb
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: 42ms
memory: 16204kb
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: 42ms
memory: 16268kb
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: 37ms
memory: 16268kb
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: 34ms
memory: 16180kb
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: 37ms
memory: 16268kb
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: 38ms
memory: 16260kb
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: 30ms
memory: 16204kb
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: 38ms
memory: 16204kb
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: 41ms
memory: 16260kb
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: 36ms
memory: 16148kb
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: 37ms
memory: 16184kb
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: 38ms
memory: 16320kb
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: 37ms
memory: 16316kb
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: 38ms
memory: 16284kb
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: 41ms
memory: 16176kb
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: 37ms
memory: 16176kb
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: 37ms
memory: 16176kb
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: 34ms
memory: 16272kb
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: 33ms
memory: 16144kb
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: 34ms
memory: 16272kb
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
Wrong Answer
time: 839ms
memory: 16704kb
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:
475780183
result:
wrong answer 1st words differ - expected: '32030707', found: '475780183'