이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e6+50;
int n,mod;
string s;
int dp[nax][3][3];
int calc(int idx,int a,int b){
if(a < 0)a = 0;
if(b < 0)b = 0;
if(a == 3)return 0;
if(b == 3)return 0;
if(idx == n)
return 1;
int &ret = dp[idx][a][b];
if(ret != -1)
return ret;
ret = 0;
ret = (calc(idx+1,a+1,b-1) + calc(idx+1,a-1,b+1)) % mod;
return ret;
}
int ans;
void solve(int idx,int a,int b){
if(a < 0)a = 0;
if(b < 0)b = 0;
if(a == 3)return;
if(b == 3)return;
if(idx == n)
return;
if(s[idx] == 'P'){
ans = (ans + calc(idx+1,a+1,b-1)) % mod;
solve(idx+1,a-1,b+1);
}else{
solve(idx+1,a+1,b-1);
}
}
int main(){
memset(dp,-1,sizeof(dp));
cin>>n>>mod>>s;
calc(0,0,0);
solve(0,0,0);
cout << (ans + 1)%mod << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |