Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #107 DIV1 B問題/DIV2 D問題 - Quantity of Strings (この記事を編集する[管理者用])

Source

Codeforces Round #107 DIV1 B問題 (500pt)
Codeforces Round #107 DIV2 D問題 (1500pt)
Problem description

問題概要

n, m, kはそれぞれ1以上2000以下.
文字の種類数はmで,n文字の文字列を作る.
ただし,任意の連続するk文字からなる部分文字列は回文になっていなければいけない.
何通り作り方があるか,mod 1000000007で求める問題.

解法

解法1:場合分け
kが1,または,kがnより大きければ,制限が無いのでm^n.
kがnに等しいなら,すべての回文が許されるので,m^(ceil(n/2)).
そうでなければ,色々試すとわかるが,自由度が少なくて,
 kが偶数ならすべて同じ文字でなければならなくて,m.
 kが奇数なら,2個置きに見ると同じ文字でなければならなくて(例えば,abababaみたいなの),m^2.
計算時間量はO(log n).

解法2:
制約が小さいので,union findでどことどこが同じ文字でなければいけないかをまとめて,m^グループ数.
計算時間量はlogとかアッカーマンの逆関数とか無視すればO(nk)ぐらい.

C言語のスパゲッティなコード (解法1)
#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 M 1000000007
#define ll long long

ll pw(ll a,ll b, ll md){
  ll r;
  if(!b) return 1;
  r = pw(a,b/2,md);
  r = (r*r)%md;
  if(b%2) r = (r*a)%md;
  return r;
}


int main(){
  int i,j,k,l,m,n;
  ll res;

  while(scanf("%d%d%d",&n,&m,&k)==3){
    if(k == 1 || k > n){
      res = pw(m, n, M);
    } else if(k == n){
      res = pw(m, (n+1)/2, M);
    } else if(k % 2 == 0){
      res = pw(m, 1, M);
    } else {
      if(n > 1) res = pw(m, 2, M);
      else      res = pw(m, 1, M);
    }

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

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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