SRM 496 Div2 Hard PalindromefulString

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11296&rd=14425

大文字アルファベットからなる長さNの文字列を想定する。この文字列中に回文となる長さMの部分文字列がK個以上あるとき、この文字列をPalindromefulな文字列という。N、M、Kが与えられるとき、Palindromefulな長さNの文字列の個数を求めよ。
2 <= N <= 11, 2 <= M <= N, 0 <= K <= 11

やりかた

Editorialを参考にしました。

CAACCもDGGDDもURRUUも c0 c1 c1 c0 c0 という形をとっているという意味では同等なものであると考えられる。つまりc0 c1 c1 c0 c0 （下のソース中では'a', 'b'などという文字に置き換えている）という構造の文字列があったときこのような形を取る文字列はc0とc1にどのアルファベットを割り当てるかなので 通りある。こんな感じで、文字列のひな形を用意して、そのひな形がPalindromefulになるなら、そこに改めて実際のアルファベットを割り当てるという感じにする。

この文字列の構造（というかひな形というべきか）の列挙はDFSでできる。
毎回の再帰で、新しい種類の文字を末尾にくっつける再帰と、すでに使用した種類の文字を末尾にくっつける再帰に分けて書けば実現できる。

以下ソース。

class PalindromfulString {
public:
  int num[11];
  int _N, _M, _K;
  ll ans;
  ll check(int a){
    ll ret = 1;
    for(int i = 0; i < a; i++) ret *= (26 - i);
    return ret == 1 ? 0 : ret;
  }

  void rec(int idx, int a, int cnt){
    if(idx == _N){
      if(cnt >= _K)
	ans += check(a);
      return;
    }
    
    for(int i = 0; i <= a; i++){
      num[idx] = i;
      if(idx >= _M - 1){
	bool palin = true;
	for(int j = 0; 2 * j <= _M - 1; j++)
	  if(num[idx - _M + 1 + j] != num[idx - j]) palin = false;
	
	if(i == a) rec(idx + 1, a + 1, palin ? cnt + 1 : cnt);
	else rec(idx + 1, a, palin ? cnt + 1 : cnt);
      }else{
	if(i == a) rec(idx + 1, a + 1, cnt);
	else rec(idx + 1, a, cnt);
      }
    }
    return;
  }
  long long count(int N, int M, int K){
    long long result;
    _N = N; _M = M; _K = K;
    ans = 0;
    rec(0, 0, 0);
    return ans;
  }
};

以前書いたもの。↓

ll P26(int k){
  ll ret = 1;
  for(int i = 1; i <= k; i++) ret = (ret * (26 - i + 1));
  return ret;
}

int _N, _M, _K;
ll ans;

void dfs(int cnt, string s, char c){
  if(cnt == _N){
    int tot = 0;
      cout << s << endl;
    //Is this type of string palindromeful?
    for(int t = 0; t < (int)s.length() - _M + 1; t++){
      bool ispal = true;
      for(int i = 0; i <= _M / 2; i++)
	if(s[t + i] != s[t + _M - 1 - i]){
	  ispal = false;
	  break;
	}
      if(ispal) tot++;
    }
    if(tot >= _K){
      ans += P26(c - 'a');//the number of ways to assign letters
    }
    return;
  }
  dfs(cnt + 1, s + c, c + 1); //concat a new type of letter
  for(char d = 'a'; d < c; d++)
    dfs(cnt + 1, s + d, c); //concat used one 
  return;
}

class PalindromfulString {
public:
  long long count(int N, int M, int K) {
    _N = N;
    _M = M;
    _K = K;
    ans = 0;
    dfs(0, "", 'a');
    return ans;
  }
};

再帰の書き方がどうしても思いつかなかった。
このやりかたは頭いいわ。ただもっとほかのやりかたもありそう。