Untitled
plain_text
a month ago
1.9 kB
6
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define TASK "lpd" #define X first #define Y second typedef pair<int, int> ii; const int M = 1e9+7; const int N = 333; int Next[N][3]; int dp[N][N][N][3]; string s; string pref_str[N]; void inc(int& v, int adder){ v += adder; v %= M; } int prefix_equal_suffix(string a, string b){ int len = b.length(); for(int res = len; res >= 0; res--){ if(pref_str[res] == b) return res; b.erase(0, 1); } } main(){ #ifndef ONLINE_JUDGE freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout); #endif int n, m, slen; cin >> n >> m >> slen; cin >> s; pref_str[0] = ""; for(int pref = 1; pref <= slen; pref++){ pref_str[pref] = pref_str[pref-1]; pref_str[pref] += s[pref-1]; } string t = ""; for(int pref = 0; pref <= slen; pref++){ if(pref) t += s[pref-1]; Next[pref][0] = prefix_equal_suffix(s, t + 'L'); Next[pref][1] = prefix_equal_suffix(s, t + 'P'); Next[pref][2] = prefix_equal_suffix(s, t + 'D'); } dp[0][0][0][0] = 1; for(int len = 0; len < n; len++) for(int nl = 0; nl <= len; nl++) for(int pref = 0; pref <= slen; pref++) for(int have = 0; have < 2; have++){ if(!dp[len][nl][pref][have]) continue; // choose l int new_pref = Next[pref][0]; int new_have = have | (new_pref == slen); inc(dp[len+1][nl+1][new_pref][new_have], dp[len][nl][pref][have]); // choose p new_pref = Next[pref][1]; new_have = have | (new_pref == slen); inc(dp[len+1][nl][new_pref][new_have], dp[len][nl][pref][have]); // choose d new_pref = Next[pref][2]; new_have = have | (new_pref == slen); inc(dp[len+1][nl][new_pref][new_have], dp[len][nl][pref][have]); } int ans = 0; for(int nl = m; nl <= n; nl++) for(int i = 0; i <= slen; i++) inc(ans, dp[n][nl][i][0]); cout << ans; }