Submission #492244

#	Time	Username	Problem	Language	Result	Execution time	Memory
492244		gg123_pe	Linear Garden (IOI08_linear_garden)	C++17	75 / 100	1590 ms	2672 KiB

linear_garden

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

typedef long long ll; 
typedef vector <int> vi; 
#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e7 + 5;


ll n, m, ans = 1, mini, maxi, pre; 
string s, wi; 

bool is_valid(string s){
    ll _mini = mini, _maxi = maxi, _pre = pre; 
    f(i,0,3){
        if(s[i] == 'L') _pre++;
        else _pre--; 
        _mini = min(_mini, _pre); 
        _maxi = max(_maxi, _pre);
    }
    return _maxi-_mini <= 2; 
}
ll bp(ll x, ll y){
    if(y == 0) return 1; 
    ll res = bp(x, y/2); res = (res*res)%m; 
    if(y%2 == 0) return res; 
    return (x*res)%m; 
}
int main(){
    cin >> n >> m >> s; 

    vector <string> c = {"LLL", "LLP", "LPL", "LPP","PLL","PLP", "PPL", "PPP"}; 

    f(i,0,n){
        if(s[i] == 'L'){
            wi.push_back('L');
            pre++;
            mini = min(mini, pre), maxi = max(maxi, pre);
            continue; 
        }
        // how many strings are there such that have lenght n-i 
        string aux = wi; 
        aux.push_back('L');

        ll k_mini = mini, k_maxi = maxi, k_pre = pre; 
        pre++;
        mini = min(mini, pre), maxi = max(maxi, pre);

        ll cant = 0, ye = n-i-1;
        for(string x: c)
            cant += is_valid(x);
        
        if(cant == 2){ // 1, 2, 2, 4, 4 ,8, 8
            // odd -> 2^(1-1), 2^(2-1)
            // 5 / 2  = 2
            ll add = bp(2, ye/2);
            //ans = (ans + add)%m; 
            //cout << aux << " " << cant << " " << ye << " " << add << endl; 
            ans = (ans + add)%m; 
        }
        if(cant == 3){ // 1, 2, 3, 5, 7, 11, 15 
            // +1, +1, +2, +2, +4, +4 
            ll add = bp(2, (ye+1)/2) - 1;
            if(ye%2 == 0){
                add = (add +  bp(1, (ye-1)/2))%m; 
            }
            //ans = (ans + add)%m; 
            ans = (ans + add)%m;
            // cout << aux << " " << cant << " " << ye << " " << add << endl; 
        }
        if(cant == 4){ // 2, 2, 4, 4, 
            // + 1 / 2
            ll add = bp(2, (ye+1)/2); 
            //ans = (ans + add)%m; 
            ans = (ans + add)%m;
            // cout << aux << " " << cant << " " << ye << " " << add << endl; 
        }
        if(cant == 5){ // 2, 3, 5, 7, 11, 15
            // +1, +2, +2, +3
            ll add = bp(2, (ye+1)/2+1) -1; 
            if(ye%2 == 1){
                add = (add - bp(2,ye/2) + m)%m;
            }
            //ans = (ans + add)%m; 
            ans = (ans + add)%m; 
            //cout << aux << " " << cant << " " << ye << " " << add << endl; 
        }
        mini = k_mini, maxi = k_maxi, pre = k_pre;
        pre--; 
        mini = min(mini, pre), maxi = max(maxi, pre);
        wi.push_back('P');
    }
    cout << ans << endl; 
    return 0;
}

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