Codeforces Good Bye 2020 G問題 - Song of the Sirens

Source

Codeforces Good Bye 2020 G問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201229-1）のコード

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

//no-unlocked
//working_memory=120m
#define L 1000000

Comb<Modint> c;
struct sval {Modint m; int sz;};
sval segtree_ph_func(sval a, sval b){ return {a.m * c.pw2(b.sz) + b.m, a.sz + b.sz}; };

int N, Q;
char S[25][2d6+50], T[1d5+2]; int len[30], mx;
char b[26][2d6+50];
char X[1d6+2]; int K, Xs;
segtree_ph<sval> t[26];

{
  rd(N,Q,S[0]@len[0],T);

  rep(k,26) t[k].walloc(N);
  rep(k,26) t[k].setN(N);
  rep(k,26) rep(i,N) t[k][i] = {0, 1};
  rep(i,N) t[T[i]-'a'][i] = {1, 1};
  rep(k,26) t[k].build();

  rep(i,1,N+1){
    len[i] = len[i-1] * 2 + 1;
    if(len[i] > 2d6+5) break;
    mx = i;
    rep(k,len[i-1]) S[i][k] = S[i][k+len[i-1]+1] = S[i-1][k];
    S[i][len[i-1]] = T[i-1];
  }

  if(len[mx] > L){
    rep(k,26){
      rep(i,L) b[k][i] = S[mx][len[mx] - L + i];
      b[k][L] = k + 'a';
      rep(i,L) b[k][L+1+i] = S[mx][i];
    }
  }

  rep(Q){
    Modint res = 0, tmp;
    rd(K,X@Xs);
    res += KMP(S[0], len[0], X, Xs);
    rep(r,1,min(K+1,mx+1)){
      res *= 2;
      if(Xs * 2 - 1 >= len[r]){
        res += KMP(S[r], len[r], X, Xs);
      } else {
        res += KMP(S[r] + len[r-1] - Xs + 1, 2 * Xs - 1, X, Xs);
      }
    }
    if(r < K+1){
      res *= c.pw2(K+1 - r);
      rep(k,26){
        tmp = KMP(b[k] + L - Xs + 1, 2 * Xs - 1, X, Xs);
        res += tmp * t[k].get(r-1, K).m;
      }
    }
    wt(res);
  }
}

Current time: 2024年04月20日18時33分29秒
Last modified: 2021年01月02日16時15分19秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Good_Bye_2020
トップページに戻る

Logged in as: unknown user (not login)