TOKI Regular Open Contest #17 H問目 - Guitar Gift

Source

TOKI Regular Open Contest #17
問題文
 Problemset (TOKI Regular Open Contest #17)

問題概要

省略

解法

省略

cLay（version 20201227-1）のコード

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

#define MD 998244353
int N, M, T, K;
char F[1d5+2], S[1d5+2];

int bc, sc, trial;
int big[1d5], small[1d5];
Mint arr1[7][2.7d5], arr2[7][2.7d5], arr[2.7d5];
{
  Mint res = 0, v;
  rd(N,M,T,K,F,S);
  rep(i,N) F[i] -= 'A';
  rep(i,K) S[i] -= 'A';
  
  trial = N - K + 1;
  sc = M / T;
  bc = sc + 1;

  rep(i,N) arr1[F[i]][i] = 1;
  rep(i,K) arr2[S[K-1-i]][i] = 1;
  rep(c,T) fft(1<<18, arr1[c]);
  rep(c,T) fft(1<<18, arr2[c]);
  REP(r,M%T) rep(c,T) rep(i,1<<18) arr[i] += arr1[c][i] * arr2[(c+r)%T][i];

  fftinv(1<<18, arr);
  v = 1 / Mint(1<<18);
  rep(i,trial) big[i] = (int)(arr[K-1+i] * v);
  rep(i,trial) small[i] = K - big[i];
  rep(i,trial) res += (Mint(sc) ** small[i]) * (Mint(bc) ** big[i]);
  wt(res);
}

Current time: 2024年04月26日06時15分44秒
Last modified: 2020年12月27日14時36分24秒 (by laycrs)
Tags: Competitive_Programming_Incomplete TOKI
トップページに戻る

Logged in as: unknown user (not login)