Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Croc Champ 2012 Round 2 B問題 - Word Cut (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 B問題 (1000pt)
Problem description

問題概要

長さNの文字列sとtが与えられる.(Nは1000以下) sを以下の操作をちょうどk回 (100000以下) 行なって,最終的にtに一致するのは何パターンあるかをmod 1000000007で求める問題.  s = xyと空でない文字列x,yに分解して,s=yxと置き直す.

解法

この操作1回分は,sの右から1文字以上N-1文字以下選び,それをsの左に移動させるというシフトを表す.
更にいうと,sの最も右の文字を左に移動させるという操作を1回~N-1回やったことに相当する.
なので,最終的に何文字分シフトされたかだけが重要で,更に,シフトされた文字数はmod Nで考えれば良い.
操作回数と何文字分シフトされたかmod Nを状態としてDPしてカウントすれば良く,愚直になるとO(Nk)だが早い言語で軽い処理をちゃんとかければ通るらしい.
実際には,何文字分シフトされたかmod Nは,1~N-1までは対称性より同じと見なせるので,O(k)でDPできる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define M 1000000007

int is_same(char A[], char B[], int len){
  int i;
  rep(i,len) if(A[i] != B[i]) return 0;
  return 1;
}

int main(){
  int i,j,k,l,m,n;
  ll dp[2], next[2];
  ll res = 0, sum;
  char A[2010], B[2010]; int len;

  scanf("%s%s%d",&A,&B,&k);
  len = strlen(A);
  if(len != strlen(B)){ puts("0"); return 0; }

  dp[0] = 1; dp[1] = 0;
  rep(m, k){
    sum = dp[0] + dp[1] * (len-1);
    dp[0] = (sum - dp[0])%M;
    dp[1] = (sum - dp[1])%M;
  }

  rep(i,len) A[i+len] = A[i];
  rep(i,len) if(is_same(A+i, B, len)){
    if(i==0) res += dp[0];
    else     res += dp[1];
  }

  res %= M;
  printf("%d\n",(int)res);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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