이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 3;
int mod;
int n;
int a[N];
int dp[2][2][2][N];
int rec(int idx, int p1, int p2, bool less){
if(idx == n){
return 1;
}
assert(a[idx]==0||a[idx]==1);
if(p1!=-1&&p2!=-1&&dp[p1][p2][less][idx]!=-1){
return dp[p1][p2][less][idx];
}
int ret = 0;
if(p1==-1||p2==-1||p1!=p2){
for(int i = 0; less? i <= 1 : i <= a[idx]; i++){
assert(i!=2);
ret += rec(idx+1,i,p1,less||(i<a[idx]));
}
} else if(p1 == 0){
if(a[idx]==1||less)ret+=rec(idx+1,1,p1,less);
}
else{
ret+=rec(idx+1,0,p1,less||a[idx]);
}
ret%=mod;
if(p1!=-1&&p2!=-1){
dp[p1][p2][less][idx]=ret;
}
return ret;
}
int main()
{
memset(dp,-1,sizeof(dp));
cin>>n>>mod;
for(int i = 0; i < n; i++){
char ch;
cin>>ch;
a[i]=ch=='P';
}
cout<<(rec(0,-1,-1,0)-1+mod)%mod;
return 0;
}
# | 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... |