Submission #234538

#	Time	Username	Problem	Language	Result	Execution time	Memory
234538		shayan_p	Ljetopica (COI19_ljetopica)	C++14	100 / 100	37 ms	8440 KiB

ljetopica

// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1010 , mod = 1e9 + 7, inf = 1e9 + 10;

int fac[maxn], ifac[maxn];

int Pow(int a, int b){
    int ans = 1;
    for(; b; b>>=1, a = 1ll * a * a % mod)
	if(b & 1)
	    ans = 1ll * ans * a % mod;
    return ans;
}
int C(int n, int k){
    if(n < 0 || k < 0 || n < k)
	return 0;
    return 1ll * fac[n] * ifac[k] %mod * ifac[n-k] % mod;
}

int S[maxn], L[maxn], R[maxn], n, k, ans;
int dp[maxn][maxn][2], tw[maxn], NW;

void go(int pos, bool ch, int used, bool needL, bool needR){
    if(used > k)
	return;
    if(pos == n-1){
	if(used == k)
	    ans = (ans + NW) % mod;
	return;
    }
    if(!needL && !needR){
	ans = (1ll * ans + 1ll * C(n-1-pos, k-used) * NW) % mod;
	ans = (1ll * ans + dp[pos][k-used][ch]) % mod;
	return;
    }
    for(int x : {0, 1}){
	if(needL && x < L[pos])
	    continue;
	if(needR && R[pos] < x)
	    continue;
	bool ch2 = S[pos] != x;
	NW = (NW + tw[n-2-pos] * x) % mod;
	go(pos+1, ch2, used + (ch != ch2), needL && x == L[pos], needR && x == R[pos]);
	NW = (NW - tw[n-2-pos] * x) % mod;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    fac[0] = 1;
    for(int i = 1; i < maxn; i++)
	fac[i] = 1ll * i * fac[i-1] % mod;
    ifac[maxn-1] = Pow(fac[maxn-1], mod-2);
    for(int i = maxn-2; i >= 0; i--)
	ifac[i] = 1ll * ifac[i+1] * (i+1) % mod;
    tw[0] = 1;
    for(int i = 1; i < maxn; i++)
	tw[i] = 2ll * tw[i-1] % mod;
    
    cin >> n >> k;
    string s, l, r;
    cin >> s >> l >> r;
    for(int i = 0; i < n-1; i++)
	S[i] = s[i] == 'R', L[i] = l[i+1] == '1', R[i] = r[i+1] == '1';
    for(int i = n-2; i >= 0; i--){
	for(int j = 0; j <= k; j++){
	    for(int w : {0, 1}){
		dp[i][j][w] = 1ll * (1ll * C(n-2-i, j) * (S[i] ^ w) + 1ll * C(n-2-i, j-1) * (S[i] ^ w ^ 1)) * tw[n-2-i] % mod;
		dp[i][j][w] = ( 1ll * dp[i][j][w] + 1ll * dp[i+1][j][w] + 1ll * (j == 0 ? 0 : dp[i+1][j-1][w ^ 1]) ) % mod;
	    }
	}
    }
    NW = tw[n-1], go(0, 0, 0, 1, 1);
    NW = tw[n-1], go(0, 1, 0, 1, 1);
    if(ans < 0)
	ans+= mod;
    return cout << ans << endl, 0;
}

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