Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2260-b62314c9
この記事にトラックバックする(FC2ブログユーザー)

SRM541 DIV1 MEDIUM - AkariDaisukiDiv1 (この記事を編集する[管理者用])

Source

TopCoder SRM541 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

長さ1以上50以下の文字列A, B, C, S, Fが与えられる.
10^7以下の正整数kが与えられる.
文字列から文字列の写像fを
 f(X) = A + X + B + X + C
で定める.ただし,ここで+記号は連結を表す.
 f^2(X) = f(f(X)), f^3(X) = f(f(f(X)))
とf^k(X)はfをk回作用させるとして,f^k(S)に部分文字列としてFは何箇所に含まれているかをmod 1000000007で求める問題.
含まれいる箇所はオーバーラップしていても良い.(その分重複して数える)

解法

XがFより長いとして,XにFが部分文字列としてn個含まれているとすると,
f(X)の中にFが何個あるかというと,
 2n + (AX の繋がってる部分でで新しく増えた分) + (XB の部分で増えた分) + (BXの分) + (XCの分)
となる.
XがFより短い間は,適当にfを作用させて,Fより長くなってから考える.
ところで,Xの最初と最後は,最終的に,AAA…,…CCCになるので,増分は一定に落ち着く.
なので,増分が一定になるまで計算して,一定になったら適当に計算を端折れば良い,

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000007
#define ll long long

class AkariDaisukiDiv1 {
public:
int countF(string Waai, string Akari, string Daisuki, string X, string F, int k) {
  ll i,j,n;
  ll in, st, ed;
  ll A, B, C;
  string ST, ED, nX;

  ll bef_minus, bef_plus;

  n = F.size();
  
  while(k && X.size() < n){
    X = Waai + X + Akari + X + Daisuki;
    k--;
  }
  if(X.size() < n) return 0;
  
  in = 0;
  rep(i,X.size()-n+1) if(X.substr(i,n) == F) in++;

  ST = X.substr(0,n);
  ED = X.substr(X.size()-n);
  X = ST + "+" + ED;
  while(k--){
    bef_minus = bef_plus = 0;
    rep(i,X.size()-n+1) if(X.substr(i,n) == F) in--, bef_minus++;

    nX = X;
    in *= 2;
    in %= M;
    X = Waai + X + Akari + X + Daisuki;

    rep(i,X.size()-n+1) if(X.substr(i,n) == F) in++, bef_plus++;
    
    ST = X.substr(0,n);
    ED = X.substr(X.size()-n);
    X = ST + "+" + ED;

    if(nX == X){
      rep(i,k){
        in -= bef_minus;
        in *= 2;
        in += bef_plus;
        in %= M;
      }
      k = 0;
    }
  }

  in %= M;
  if(in < 0) in += M;

  return in;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2260-b62314c9
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。