codeforce 1400
COFO::1245C Constanze's Machine
cofo problem
COFO::1245C Constanze’s Machine
Problem
- level : 1400
- tag : dp
- TIME
- to understand : 10
- to algorithm : 25
- to code : 10
- to debug : 8
- understaing edit : 1
Point
- Constanze 가 string 알파벳 소문자로 이루어진 문자열 s1을 만들어두었습니다.
- 이때, Akko라는 친구가 s1에 포함된
- ‘w’를 ‘uu’로 바꾸고
- ‘m’을 ‘nn’으로 바꾸도록 문자열을 수정했습니다.
- 해당 수정된 문자열이 주어질때, Akko때문에 바뀌기 전 문자열의 가능성의 갯수를 출력합니다.
Design
- 연속으로 주어지는 n과 u에 대해서 각 가능성의 갯수를 구해줘야합니다.
- 하지만, n이던 u이던 각각 연속된 갯수가 같으면 가능성의 갯수가 같습니다.
- 따라서, 연속된 u와 n의 집합의 갯수와 사이즈를 미리 벡터에 넣어둡니다.
- 이후, 하나씩 꺼내며 해당 길이의 연속된 문자열 u or n에 대해서 가능성의 갯수를 구하고 이들을 곱해주면 됩니다.
- 이때, 해당 가능성은 길이에 대해 피보나치 수열 규칙을 가지므로, dp로 처리할 수 있습니다.
Complexity
- O(N)
Code
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
string s;
ull dp[100005];
ull MOD = 1e9 + 7;
void get_series(char what, vector<ull>& v){
bool f = false;
int cnt = 0;
rep(i, 0, s.size()){
if(s[i] == what){
f = true;
cnt++;
}
else{
if(cnt > 1) v.push_back(cnt);
cnt = 0;
f = false;
}
}
if(cnt > 1) v.push_back(cnt);
}
ull fibonacci(ull i){
if(i < 0) return 0;
if(dp[i]) return dp[i];
return dp[i] = (fibonacci(i-1) % MOD + fibonacci(i-2) % MOD) % MOD;
}
void solve(){
cin >> s;
ull ans = 1;
vector<ull> v;
// exception
bool f = false;
rep(i, 0, s.size()) if(s[i] == 'm' || s[i] == 'w'){
f = true;
break;
}
if(f){
cout << "0" << '\n';
return;
}
// fibonacci
dp[0] = 0, dp[1] = 1, dp[2] = 2;
get_series('u', v);
get_series('n', v);
rep(i, 0, v.size()) ans = (ans * fibonacci(v[i])) % MOD;
if(v.size() == 0) cout << 1 << '\n';
else cout << ans << '\n';
}
int main(){
solve();
return 0;
}