Submission #1340246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340246		JungPS	Linear Garden (IOI08_linear_garden)	C++20	2 / 100	1595 ms	1504 KiB

linear_garden

#include<bits/stdc++.h>
using namespace std;

#define int long long
int MOD;
int split;
int n; 
int ans;
string str;
int power(int a,int b){
    if(b==0) return 1;
    if(b==1) return a;
    int tmp=pow(a,b/2);
    if(b%2) return tmp*tmp%MOD*a%MOD;
    else return tmp*tmp%MOD;
}

void recur(int x,int shard,int pw,int prev,bool trig){
    if(x==str.size()+1) return ;
    ans+=(str[x-1]=='P')*(prev-shard+MOD)%MOD;
    ans%=MOD;
    int a=power(2,pw/2)%MOD;
    int b=(shard-power(2,pw/2)%MOD+MOD)%MOD;
    if(a==0) a=b;
    if(b==0) b=a;
    if(((str[0]=='P')+(x%2)+(str[x]=='P'))%2){
        recur(x+1,a%MOD,pw,shard,trig);
    }
    else{
        if(a==b && !trig) recur(x+1,b%MOD,pw,shard,true);
        recur(x+1,b%MOD,pw,shard,trig);
    }
    //recur(x+1,shard);
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> MOD;
    cin >> str;
    if(n%2){
        split=(2*power(2,n/2)%MOD-1+MOD)%MOD;
    }
    else{
        split=(3*power(2,n/2-1)%MOD-1+MOD)%MOD;
    }
    recur(1,split,n-2,(split*2)%MOD,false);
    cout << (ans+1)%MOD;
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5