QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133840 | #4939. Red Black Ball | salvator_noster | WA | 4ms | 120140kb | C++14 | 2.4kb | 2023-08-02 15:13:44 | 2023-08-02 15:13:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(ll i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(ll i=hd[a],y;(y=to[i]);i=nxt[i])
#define Mod(x) (x>=P)&&(x-=P)
typedef long long ll;
char IO;
ll rd(ll res=0){
bool f=0;
while(IO=getchar(),IO<48||IO>57)
f|=IO=='-';
do res=(res<<1)+(res<<3)+(IO^48);
while(isdigit(IO=getchar()));
return f?-res:res;
}
void Max(ll &x,ll y){x<y&&(x=y);}
const ll M=155,P=998244353;
ll n,dp[M][M][M*2][2],C[M][M],ans[M*2][2],m;
struct node{
ll x,c;
bool operator <(const node &_)const{
return x<_.x;
}
}p[M];
ll dfs(ll l,ll r,ll cl,ll dis){
if(l==r-1){
return dis==0;
}
if(dis+n<0)return 0;
if(~dp[l][r][dis+n][cl])return dp[l][r][dis+n][cl];
ll res=0;
rep(k,l+1,r-1){
if(p[k].x-p[l].x<=p[r].x-p[k].x){
if(cl)res+=dfs(k,r,cl,dis-(k-l))*C[r-l-2][r-k-1]%P,Mod(res);
else res+=dfs(k,r,cl,dis+(k-l))*C[r-l-2][r-k-1]%P,Mod(res);
}else{
if(!cl)res+=dfs(l,k,cl,dis-(r-k))*C[r-l-2][r-k-1]%P,Mod(res);
else res+=dfs(l,k,cl,dis+(r-k))*C[r-l-2][r-k-1]%P,Mod(res);
}
}
return dp[l][r][dis+n][cl]=res;
}
char s[10];
int fac[M];
int main(){
memset(dp,-1,sizeof dp);
n=rd(),m=rd();
rep(i,1,n){
p[i].x=rd();
scanf("%s",s);
if(*s=='B')p[i].c=2;
else p[i].c=1;
}
rep(i,1,m)p[i+n].x=rd();
n+=m;
rep(i,fac[0]=1,n)fac[i]=fac[i-1]*i%P;
sort(p+1,p+n+1);
rep(i,0,n)rep(j,C[i][0]=1,i)
C[i][j]=C[i-1][j]+C[i-1][j-1],Mod(C[i][j]);
ll L,R;
rep(i,1,n)if(p[i].c)R=i;
drep(i,n,1)if(p[i].c)L=i;
ll t=0,cnt=0;
if(p[L].c==1)t+=L-1;
else t-=L-1;
if(p[R].c==1)t+=n-R;
else t-=n-R;
cnt=L-1+n-R;
rep(i,1,n)t+=(p[i].c==1)-(p[i].c==2);
ans[t+n][0]=fac[n-R]*fac[L-1]%P*C[L-1+n-R][L-1]%P;
ll tl=L;
rep(i,L+1,n){
if(p[i].c){
cnt+=i-tl-1;
if(p[i].c==p[tl].c){
if(p[i].c==2){
rep(j,-n,n)if(j-(i-tl-1)+n>=0)
ans[j-(i-tl-1)+n][1]+=ans[j+n][0]*C[cnt][i-tl-1]%P*fac[i-tl-1]%P,Mod(ans[j-(i-tl-1)+n][1]);
}else{
rep(j,-n,n)
ans[j+(i-tl-1)+n][1]+=ans[j+n][0]*C[cnt][i-tl-1]%P*fac[i-tl-1]%P,Mod(ans[j+(i-tl-1)+n][1]);
}
}else{
rep(j,-n,n)rep(k,-n,n)if(j+k+n>=0)
ans[j+k+n][1]+=ans[j+n][0]*dfs(tl,i,2-p[tl].c,k)%P*C[cnt][i-tl-1]%P,Mod(ans[j+k+n][1]);
}
tl=i;
rep(j,-n,n)ans[j+n][0]=ans[j+n][1],ans[j+n][1]=0;
}
}
ll res=0;
rep(i,1,n)res+=ans[i+n][0],Mod(res);
printf("%lld",res);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 120020kb
input:
2 3 1 BLACK 10 RED 2 5 7
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 3ms
memory: 120064kb
input:
2 3 1 RED 10 BLACK 2 4 7
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 4ms
memory: 120052kb
input:
2 3 1 RED 10 BLACK 7 4 2
output:
6
result:
ok single line: '6'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 120140kb
input:
20 46 238846592 BLACK 199923217 RED 526626128 BLACK 62308338 RED 523811748 RED 59432 BLACK 273113193 BLACK 730729301 BLACK 973259012 RED 225318015 BLACK 611574923 RED 234880345 RED 485448383 BLACK 405607946 BLACK 747693124 RED 794086621 BLACK 91585417 BLACK 466451303 RED 244184598 RED 334788273 RED ...
output:
748106537
result:
wrong answer 1st lines differ - expected: '850819974', found: '748106537'