Codeforces Global Round 4 F2問題 (1500pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
#define MD 998244353
int N, M;
int C[1d6];
int vis[1000][1000];
mint dp[1000][1000];
int gmn[500], gmx[500];
mint solve(int a, int b){
int i, j, k, mn, mx, dame;
mint lef, rig, mul;
if(a > b) return 1;
if(vis[a][b]) return dp[a][b];
vis[a][b] = 1;
j = int_inf;
rep(i,a,b+1) j <?= C[i];
mn = gmn[j];
mx = gmx[j];
lef = rig = 0;
dame = mn;
for(i=mn;i>=a;i--){
dame <?= gmn[C[i]];
if(i <= dame) lef += solve(a,i-1) * solve(i,mn-1);
}
dame = mx;
for(i=mx;i<=b;i++){
dame >?= gmx[C[i]];
if(i >= dame) rig += solve(mx+1,i) * solve(i+1,b);
}
mul = 1;
rep(i,mn,mx+1){
if(C[i]==j) continue;
k = i;
while(C[k+1]!=j) k++;
mul *= solve(i,k);
i = k;
}
return dp[a][b] = lef * rig * mul;
}
{
int i, j, k, mn, mx;
mint res;
rd(N,M,(C--)(M));
k = 1;
rep(i,1,M){
if(C[i]==C[i-1]) continue;
C[k++] = C[i];
}
M = k;
if(M > 2N){
wt(0);
return 0;
}
rep(i,N) gmn[i] = M;
rep(i,N) gmx[i] = -1;
rep(i,M) gmn[C[i]] <?= i;
rep(i,M) gmx[C[i]] >?= i;
rep(k,N){
rep(i,gmn[k]+1,gmx[k]) if(C[i] < k){
wt(0);
return 0;
}
}
res = solve(0, M-1);
wt(res);
}
Current time: 2024年03月28日18時57分55秒
Last modified: 2019年07月21日16時02分06秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Global_Round_4
トップページに戻る
Logged in as: unknown user (not login)