読者です 読者をやめる 読者になる 読者になる

天下一予選B B - エターナルスタティックファイナル

解法

dp[文字数] := 覚えている呪文全てを考慮したとき、新しい呪文の先頭から文字数分の文字列を生成する場合数

反省
自分で文字を決めるとき、 N, M とかだと字面が似てて間違えやすい。本番は以下の NEWSIZE を M と書いていて、そのバグで詰まっていた。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD (1000000007)

int main() {
  
  ll dp[1010] = {};
  
  int N; cin >> N;
  int NEWSIZE;
  string NEW; cin >> NEW;
  NEWSIZE = NEW.size();
  vector<string> vec(N);
  rep(i, N) {
    cin >> vec[i];
  }
  
  dp[0] = 1;
  rep(i, NEWSIZE) {
    rep(j, N) {
      int const ssize = vec[j].size();
      if(i+ssize > NEWSIZE) continue;
      if(string(NEW.begin()+i, NEW.begin()+i+ssize) == vec[j]) {
	(dp[i+ssize] += dp[i]) %= MOD;
      }
    }
  }
  
  cout << dp[NEWSIZE]%MOD << endl;
  
  return 0;
}