Submission #702125

#	Time	Username	Problem	Language	Result	Execution time	Memory
702125		bin9638	Ljetopica (COI19_ljetopica)	C++17	100 / 100	40 ms	32332 KiB

ljetopica

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define N  1010
#define fs first
#define sc second
#define ii pair<int,int>
#define iii pair<ii,int>
#define ld long double
#define pb push_back
#define int ll

const ll mod=1e9+7;

int mu2[N],n,k,a[N];
vector<int>l,r,dq;
ii dp[N][N][2];

void selfadd(int&u,int v)
{
    u=(u+v)%mod;
}

ii get(int pos,int k,int id,int dabe)
{
    if(pos==0)
        return{0,(k==0)};
    if(dabe&&dp[pos][k][id].fs!=-1)
        return dp[pos][k][id];
    ii res={0,0};
   // cout<<pos<<" "<<k<<" "<<id<<endl;
    //ko doi
    int i=(id^a[pos]);
    if(dabe||i<=dq[pos-1])
    {
        ii cc=get(pos-1,k,id,(dabe|(i<dq[pos-1])));
        selfadd(res.fs,cc.fs+cc.sc*mu2[pos-1]*i);
        selfadd(res.sc,cc.sc);
    }
    if(k>0)
    {
        i=((id^a[pos])^1);
        if(dabe||i<=dq[pos-1])
        {
            ii cc=get(pos-1,k-1,(id^1),(dabe|(i<dq[pos-1])));
            selfadd(res.fs,cc.fs+cc.sc*mu2[pos-1]*i);
            selfadd(res.sc,cc.sc);
        }
    }
    if(dabe)
        dp[pos][k][id]=res;
    return res;
}

int solve(vector<int>s)
{
    //for(int i=n-1;i>=0;i--)cout<<s[i]<<" ";
    if(s[n-1]==0)
        return 0;
    dq=s;
    ii A=get(n-1,k,0,0),B=get(n-1,k,1,0);
    selfadd(A.fs,B.fs);
    selfadd(A.sc,B.sc);
    return(A.fs+A.sc*mu2[n-1])%mod;
}

int32_t main()
{
   // freopen("A.inp","r",stdin);
   // freopen("A.out","w",stdout);
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(0);
    cin>>n>>k;
    for(int i=n-1;i>=1;i--)
    {
        char ch;
        cin>>ch;
        a[i]=(ch=='R');
    }
    mu2[0]=1;
    for(int i=1;i<=n;i++)
        mu2[i]=mu2[i-1]*2%mod;
    l.resize(n+1,0);
    r.resize(n+1,0);
    for(int i=n-1;i>=0;i--)
    {
        char ch;
        cin>>ch;
        l[i]=ch-'0';
     //   cin>>l[i];
    }
    for(int i=n-1;i>=0;i--)
    {
        char ch;
        cin>>ch;
        r[i]=ch-'0';
    }
    for(int i=0;i<=1005;i++)
        for(int j=0;j<=1005;j++)
            dp[i][j][0]=dp[i][j][1]={-1,-1};
    int res=solve(r);
    for(int i=0;i<=n-1;i++)
        if(l[i]==1)
        {
            l[i]=0;
            for(int j=0;j<i;j++)
                l[j]=1;
            break;
        }
    cout<<(res-solve(l)+mod*mod)%mod;
    return 0;
}

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