TOKI Regular Open Contest #17
問題文
Problemset (TOKI Regular Open Contest #17)
省略
省略
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月25日16時38分42秒
Last modified: 2020年12月27日14時36分24秒 (by laycrs)
Tags: Competitive_Programming_Incomplete TOKI
トップページに戻る
Logged in as: unknown user (not login)