Submission #144127

#	Time	Username	Problem	Language	Result	Execution time	Memory
144127		Abelyan	Ljetopica (COI19_ljetopica)	C++17	100 / 100	166 ms	71296 KiB

ljetopica

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=2e3+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

ll dp[N][N][2][2][2],qan[N][N][2][2][2],P[N];
int s[N],a[N],b[N],qan0,qan1;
bool col0,col1;
char tv;


int main(){
    fastio;
    srng;
    int n,k;
    cin>>n>>k;
    n--;
    FOR(i,n){
        char c;
        cin>>c;
        if (c=='L')s[i]=0;
        else s[i]=1;

    }
    FOR(i,2*n){
        if (!i)P[i]=1;
        else P[i]=(P[i-1]*2ll)%MOD;
    }

    cin>>tv;
    if (tv==0)assert(0);
    FOR(i,n){
        char c;
        cin>>c;
        a[i]=c-'0';
        if (tv=='0')a[i]=0;
    }
    cin>>tv;
    if (tv=='0'){
        assert(0);
        cout<<0<<endl;
        return 0;
    }
    FOR(i,n){
        char c;
        cin>>c;
        b[i]=c-'0';
    }
    FOR(pla,2)FOR(plb,2)FOR(hak,2)qan[n][0][pla][plb][hak]=1;
    //cout<<n<<endl;
    FORD(i,n){
        //cout<<i<<endl;
        FOR(j,k+1){
            if (n-i<j)continue;
            //cout<<1<<endl;
            FOR(pla,2){
                FOR(plb,2){
                    FOR(hak,2){
                        if (hak)s[i]=1-s[i];
                        qan0=0;
                        qan1=0;
                        col0=true;
                        col1=true;
                        if ((pla && a[i]) || (!j && s[i])){
                            col0=false;
                        }
                        if ((plb && !b[i]) || (!j && !s[i])){
                            col1=false;
                        }
                        //cout<<pla<<" "<<plb<<" "<<i<<" "<<col0<<" "<<col1<<endl;
                        if (s[i]==0)qan1=1;
                        if (s[i]==1)qan0=1;
                        int la1=pla;
                        if (a[i]==0)la1=0;
                        int lb0=plb;
                        if (b[i]==1)lb0=0;
                        if (col0){
                            int pox=(hak+qan0)%2;
                            dp[i][j][pla][plb][hak]+=dp[i+1][j-qan0][pla][lb0][pox];
                            dp[i][j][pla][plb][hak]%=MOD;
                            qan[i][j][pla][plb][hak]+=qan[i+1][j-qan0][pla][lb0][pox];
                            qan[i][j][pla][plb][hak]%=MOD;
                        }
                        if (col1){
                            int pox=(hak+qan1)%2;
                            /*
                            if (hak && !i && pla==plb && pla){
                                cout<<la1<<endl;
                            }*/
                            dp[i][j][pla][plb][hak]+=(dp[i+1][j-qan1][la1][plb][pox]+(qan[i+1][j-qan1][la1][plb][pox]*P[n-i-1])%MOD)%MOD;
                            dp[i][j][pla][plb][hak]%=MOD;
                            qan[i][j][pla][plb][hak]+=qan[i+1][j-qan1][la1][plb][pox];
                            qan[i][j][pla][plb][hak]%=MOD;
                        }
                        if (hak)s[i]=1-s[i];
                        //if (hak)
                            //cout<<i<<" "<<pla<<" "<<plb<<" "<<dp[i][j][pla][plb][hak]<<" "<<qan[i][j][pla][plb][hak]<<" "<<col0<<" "<<col1<<endl;
                    }
                }
            }
        }
    }

    //cout<<dp[0][k][1][1]<<endl;
    dp[0][k][1][1][0]+=(qan[0][k][1][1][0]*P[n])%MOD;
    dp[0][k][1][1][0]%=MOD;
    dp[0][k][1][1][1]+=(qan[0][k][1][1][1]*P[n])%MOD;
    dp[0][k][1][1][1]%=MOD;
    //cout<<qan[0][k][1][1]<<endl;
    //assert(dp[0][k][1][1][1]>=0 && dp[0][k][1][1][0]>=0);
    cout<<(dp[0][k][1][1][1]+dp[0][k][1][1][0])%MOD<<endl;
    return 0;
}
/*
7 2 8
C 1
C 2
C 3
C 4
C 5
C 6
O 7
O 7

*/

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61