Submission #683762

#	Time	Username	Problem	Language	Result	Execution time	Memory
683762		MtSaka	Ljetopica (COI19_ljetopica)	C++17	100 / 100	89 ms	340 KiB

ljetopica

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
static constexpr long long MOD=1000000007;
int main(){
  int n,k;cin>>n>>k;
  string s;cin>>s;
  string a,b;cin>>a>>b;
  //cerr<<n<<" "<<k<<endl;
  //cerr<<s<<endl;
  //cerr<<a<<" "<<b<<endl;
  auto f=[&](const string&t)->ll {
    //cerr<<t<<" "<<s<<endl;
    array<vector<ll>,2>dp;
    array<vector<ll>,2>sum;
    dp[0]=vector<ll>(k+1,0);
    dp[1]=vector<ll>(k+1,0);
    sum[0]=vector<ll>(k+1,0);
    sum[1]=vector<ll>(k+1,0);
    if(t[0]=='1'){
      dp[0][0]=1;
      sum[0][0]=1;
    }
    else{
      dp[1][0]=1;
      sum[1][0]=1;
    }
    //for(int i=0;i<=k;i++)cerr<<dp[0][i]<<" \n"[i==k];
    //for(int i=0;i<=k;i++)cerr<<dp[1][i]<<" \n"[i==k];
    //cerr<<endl;
    for(int i=1;i<n;i++){
      array<vector<ll>,2>dp2;
      array<vector<ll>,2>sum2;
      dp2[0]=vector<ll>(k+1,0);
      dp2[1]=vector<ll>(k+1,0);
      sum2[0]=vector<ll>(k+1,0);
      sum2[1]=vector<ll>(k+1,0);
      for(int j=0;j<=k;j++){
        if(j+1<=k){
          dp2[1][j+1]+=dp[1][j];
          if((j+1)&1){
            if(s[i-1]=='L'){
              sum2[1][j+1]+=sum[1][j]*2+dp[1][j];
              if(t[i]=='1')dp2[0][j+1]+=dp[0][j],sum2[0][j+1]+=sum[0][j]*2+dp[0][j];
            }
            else{
              sum2[1][j+1]+=sum[1][j]*2;
              if(t[i]=='1')dp2[1][j+1]+=dp[0][j],sum2[1][j+1]+=sum[0][j]*2;
              else dp2[0][j+1]+=dp[0][j],sum2[0][j+1]+=sum[0][j]*2;
            }
          }
          else{
            if(s[i-1]=='L'){
              sum2[1][j+1]+=sum[1][j]*2;
              if(t[i]=='1')dp2[1][j+1]+=dp[0][j],sum2[1][j+1]+=sum[0][j]*2;
              else dp2[0][j+1]+=dp[0][j],sum2[0][j+1]+=sum[0][j]*2;
            }
            else{
              sum2[1][j+1]+=sum[1][j]*2+dp[1][j];
              if(t[i]=='1')dp2[0][j+1]+=dp[0][j],sum2[0][j+1]+=sum[0][j]*2+dp[0][j];
            }
          }
          dp2[0][j+1]%=MOD;
          dp2[1][j+1]%=MOD;
          sum2[0][j+1]%=MOD;
          sum2[1][j+1]%=MOD;
        }
        dp2[1][j]+=dp[1][j];
        if(j&1){
          if(s[i-1]=='L'){
            sum2[1][j]+=sum[1][j]*2+dp[1][j];
            if(t[i]=='1')dp2[0][j]+=dp[0][j],sum2[0][j]+=sum[0][j]*2+dp[0][j];
          }
          else{
            sum2[1][j]+=sum[1][j]*2;
            if(t[i]=='1')dp2[1][j]+=dp[0][j],sum2[1][j]+=sum[0][j]*2;
            else dp2[0][j]+=dp[0][j],sum2[0][j]+=sum[0][j]*2;
          }
        }
        else{
          if(s[i-1]=='L'){
            sum2[1][j]+=sum[1][j]*2;
            if(t[i]=='1')dp2[1][j]+=dp[0][j],sum2[1][j]+=sum[0][j]*2;
            else dp2[0][j]+=dp[0][j],sum2[0][j]+=sum[0][j]*2;
          }
          else{
            sum2[1][j]+=sum[1][j]*2+dp[1][j];
            if(t[i]=='1')dp2[0][j]+=dp[0][j],sum2[0][j]+=sum[0][j]*2+dp[0][j];
          }
        }
        dp2[0][j]%=MOD;
        dp2[1][j]%=MOD;
        sum2[0][j]%=MOD;
        sum2[1][j]%=MOD;
      }
      swap(dp,dp2);
      swap(sum,sum2);
      //for(int j=0;j<=k;j++)cerr<<dp[0][j]<<" \n"[j==k];
      //for(int j=0;j<=k;j++)cerr<<dp[1][j]<<" \n"[j==k];
      //cerr<<endl;
    }
    return sum[0][k]+sum[1][k];
  };
  ll ans=0;
  int id=n-1;
  while(a[id]!='1'){
    a[id]='1';
    id--;
  }
  a[id]='0';
  ans=f(b)-f(a)+MOD;
  for(auto&i:s){
    if(i=='L')i='R';
    else i='L';
  }
  ans+=f(b)-f(a)+MOD;
  ans%=MOD;
  cout<<ans<<endl;
}

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