Educational Codeforces Round 104 G問題 - String Counting

Source

Educational Codeforces Round 104 G問題
Problem description

問題概要

省略

解法

省略

cLay（version 20210227-1）のコード

C++に変換後のコードはこちら

//no-unlocked
#define MD 998244353
int N, M = 26, A[26];
Modint dp[3][3][201][201], nx[3][3][201][201];
{
  int mx = 0;
  Modint res = 1;
  rd(N,A(M));

  rep(i,N) if(i%4 < 2) mx++;

  rep(i,N) res *= if[i < 2, M, M-1];

  rep(x,3) rep(y,3) rep(i,mx+1) rep(j,mx+1) dp[x][y][i][j] = 0;
  dp[0][0][0][0] = 1;
  rep(t,N){
    rep(x,3) rep(y,3) rep(i,mx+1) rep(j,mx+1) nx[x][y][i][j] = 0;

    rep(x,3) rep(y,3) rep(i,mx+1) rep(j,mx+1) nx[y][0][i][j] += dp[x][y][i][j] * (if[x==0&&t>=2, M-3, M-2]);

    rep(x,3) if(x!=1) rep(y,3) rep(i,mx) rep(j,mx+1) nx[y][1][i+1][j] += dp[x][y][i][j];
    rep(x,3) if(x!=2) rep(y,3) rep(i,mx+1) rep(j,mx) nx[y][2][i][j+1] += dp[x][y][i][j];

    rep(x,3) rep(y,3) rep(i,mx+1) rep(j,mx+1) dp[x][y][i][j] = nx[x][y][i][j];
  }

  rep(k,M) rep(i,A[k]+1,mx+1) rep(j,mx+1){
    rep(x,3) rep(y,3) res -= dp[x][y][i][j];
  }
  rep(k,M) rep(l,k+1,M) rep(i,A[k]+1,mx+1) rep(j,A[l]+1,mx+1){
    rep(x,3) rep(y,3) res += dp[x][y][i][j];
  }

  wt(res);
}

Current time: 2024年04月20日12時10分34秒
Last modified: 2021年02月27日13時02分36秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る

Logged in as: unknown user (not login)

ログイン：