東京工業大学プログラミングコンテスト2019 G問題 - Palindromic Love Letter

Source

東京工業大学プログラミングコンテスト2019
問題文

問題概要

省略

解法

省略

cLayversion 20190830-1)のコード

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

int N, K; char T[200002];
mint dp[100001];
{
  int i, j, k;
  int m = 0, s = 0, d = 0;
  mint res, tmp;
  combination_mint c;

  c.init(100001);
  
  rd(N,K,T);
  rep(i,N/2) if[T[i]==T[N-1-i], s, d]++;
  if(N%2) m++;

  dp[0] = 1;
  rep(i,1,s+1) dp[i] = c.C(s,i) * ((mint(25)) ** i) + dp[i-1];

  res = 0;
  rep(i,d+1) rep(j,m+1){
    k = K - i - d - j;
    if(k < 0) break;
    if(k==1 && i==0 && j==0 && d==0) continue;

    tmp = c.C(d,i);
    if(j == 1) tmp *= 25;
    tmp *= (mint(2)) ** (d-i);
    tmp *= (mint(24)) ** i;

    res += tmp * dp[min(s,k/2)];
  }

  wt(res);
}

Current time: 2021年09月28日23時46分15秒
Last modified: 2019年09月01日00時50分47秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: