QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#867197 | #8820. Exchanging Kubic 2 | lsj2009 | WA | 56ms | 3840kb | C++14 | 3.3kb | 2025-01-23 10:46:00 | 2025-01-23 10:46: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) {
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,-n,800) {
int p=0;
rep(i,0,n) {
rep(k,0,1) {
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 29ms
memory: 3840kb
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: 29ms
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: 56ms
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: -100
Wrong Answer
time: 55ms
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:
4148600
result:
wrong answer 1st words differ - expected: '625955', found: '4148600'