Submission #1118658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118658		vjudge1	Ljetopica (COI19_ljetopica)	C++14	39 / 100	11 ms	11872 KiB

ljetopica

#include<cstdio>
#include<cstring>
#include<algorithm>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

const ll mod=1e9+7;
const int NV=1e3;
int p2[NV+5],C[NV+5][NV+5];

namespace xm{
    int f[NV+5][NV+5][2],lpv[NV+5],rpv[NV+5];
    char sz[NV+5],ls[NV+5],rs[NV+5];
    void _(){
        int N,K;

        p2[0]=1;
        for(int i=1;i<NV+5;++i) p2[i]=p2[i-1]*2ll%mod;
        for(int i=0;i<NV+5;++i){
            C[i][0]=1;
            for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }

        scanf("%d%d%s%s%s",&N,&K,sz+1,ls+1,rs+1);
        lpv[1]=rpv[1]=1;
        for(int i=2;i<=N;++i){
            lpv[i]=(lpv[i-1]*2ll+ls[i]-'0')%mod;
            rpv[i]=(rpv[i-1]*2ll+rs[i]-'0')%mod;
        }

        f[0][0][0]=f[0][0][1]=0;
        for(int i=1;i<=N-1;++i) for(int j=0;j<=i&&j<=K;++j){
            f[i][j][0]=(f[i-1][j][0]+ll(j?f[i-1][j-1][1]:0)+(sz[N-i]=='R'||j?(ll)p2[i-1]*C[i-1][j-(sz[N-i]=='L')]:0))%mod;
            f[i][j][1]=(f[i-1][j][1]+ll(j?f[i-1][j-1][0]:0)+(sz[N-i]=='L'||j?(ll)p2[i-1]*C[i-1][j-(sz[N-i]=='R')]:0))%mod;
            //printf("%d %d %d %d\n",i,j,f[i][j][0],f[i][j][1]);
        }
        ll ans=(f[N-1][K][0]+f[N-1][K][1]+(ll)p2[N]*C[N-1][K])%mod;
        //printf("%lld\n",ans);
        auto getlval=[&](int x,int f){
            int cnt=0;
            for(int i=2;i<=x;++i){
                if((ls[i]=='0')^(sz[i-1]=='L')^f^(i==x)){
                    ++cnt;
                    f^=1;
                }
            }
            return mkp(cnt,f);
        };
        for(int i=N;i>1;--i) if(ls[i]=='1'){
            auto csm=getlval(i,0);
            //printf("%d %d\n",csm.fi,csm.se);
            //printf("%lld %lld\n",f[N-i][K-csm.fi][csm.se],(ll)C[N-i][K-csm.fi]*p2[N-i+1]%mod*lpv[i-1]%mod);
            if(csm.fi<=K) ans=(ans-f[N-i][K-csm.fi][csm.se]-(ll)C[N-i][K-csm.fi]*p2[N-i+1]%mod*lpv[i-1])%mod;
            csm=getlval(i,1);
            //printf("%d %d\n",csm.fi,csm.se);
            //printf("%lld %lld\n",f[N-i][K-csm.fi][csm.se],(ll)C[N-i][K-csm.fi]*p2[N-i+1]%mod*lpv[i-1]%mod);
            if(csm.fi<=K) ans=(ans-f[N-i][K-csm.fi][csm.se]-(ll)C[N-i][K-csm.fi]*p2[N-i+1]%mod*lpv[i-1])%mod;
        }
        auto getrval=[&](int x,int f){
            int cnt=0;
            for(int i=2;i<=x;++i){
                if((rs[i]=='0')^(sz[i-1]=='L')^f^(i==x)){
                    ++cnt;
                    f^=1;
                }
            }
            return mkp(cnt,f);
        };
        //printf("%lld\n",ans);
        for(int i=N;i>1;--i) if(rs[i]=='0'){
            auto csm=getrval(i,0);
            //printf("%lld\n",f[N-i][K-csm.fi][csm.se]);
            if(csm.fi<=K) ans=(ans-f[N-i][K-csm.fi][csm.se]-C[N-i][K-csm.fi]*((ll)p2[N-i+1]*rpv[i-1]+p2[N-i]))%mod;
            csm=getrval(i,1);
            //printf("%d %d\n",csm.fi,csm.se);
            //printf("%d %d %d %lld\n",N-i,K-csm.fi,csm.se,f[N-i][K-csm.fi][csm.se]);
            if(csm.fi<=K) ans=(ans-f[N-i][K-csm.fi][csm.se]-C[N-i][K-csm.fi]*((ll)p2[N-i+1]*rpv[i-1]+p2[N-i]))%mod;
        }
        printf("%lld\n",(ans+mod)%mod);
    }
}

int main(){
    xm::_();
    return 0;
}

Compilation message (stderr)

ljetopica.cpp: In function 'void xm::_()':
ljetopica.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d%d%s%s%s",&N,&K,sz+1,ls+1,rs+1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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