Submission #751061

#TimeUsernameProblemLanguageResultExecution timeMemory
751061Username4132Ljetopica (COI19_ljetopica)C++14
0 / 100
16 ms11260 KiB
#include<iostream> using namespace std; using ll = long long; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define forsn(i, s, n) for(int i=s; i<(int)n; ++i) const int MAXN=1010, MOD=1000000007; int n, k, pot[MAXN], comb[MAXN][MAXN], dp[MAXN][MAXN][2]; string dirs, le, ri; void pre(string& num){ int pos=num.size()-1; while(num[pos]=='0') num[pos--]='1'; num[pos]='0'; } void nxt(string& num){ int pos=num.size()-1; while(num[pos]=='1') num[pos--]='0'; num[pos]='1'; } int calc(string num){ int ret=0; forn(dir, 2){ int xtra=0, sum=0; bool cur=dir; forsn(i, 1, num.size()){ bool differs=cur^(num[i]=='0')^(dirs[i-1]=='L'); xtra+=(int)differs; cur^=differs; } forn(i, num.size()) if(num[i]=='1') sum=(sum + pot[n-1-i])%MOD; if(xtra<=k) ret=(ret+dp[n-num.size()][k+1-xtra][cur]+((ll)comb[n-num.size()][k+1-xtra])*sum)%MOD; } return ret; } int query(string l, string r){ int ret=0; for(; l<=r; l.pop_back(), r.pop_back()){ if(l.back()=='1') ret+=calc(l), nxt(l); if(r.back()=='0') ret+=calc(r), pre(r); } return ret; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k >> dirs >> le >> ri; pot[0]=1; forn(i, n) pot[i+1]=(pot[i]<<1)%MOD; forn(i, n+1) comb[i][1]=comb[i][i+1]=1; forsn(i, 2, n+1) forsn(j, 1, n) comb[i][j+1]=(comb[i-1][j+1]+comb[i-1][j])%MOD; forsn(i, 1, n) forsn(j, 1, i+2) forn(d, 2){ dp[i][j][d]=(dp[i-1][j][d] + dp[i-1][j-1][d^1] + comb[i-1][j-(d^(dirs[n-i-1]=='L'))]*((ll)pot[i-1]))%MOD; } cout << query(le, ri) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...