Submission #234757

#	Time	Username	Problem	Language	Result	Execution time	Memory
234757		amoo_safar	Ljetopica (COI19_ljetopica)	C++14	100 / 100	187 ms	64380 KiB

ljetopica

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 1e3 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

str t;
int n, k, ss[N];
ll dp[N][N][2][2];
ll cnt[N][N][2][2];

int fl = 1;
ll Solve(str s){
	memset(dp, 0, sizeof dp);
	memset(cnt, 0, sizeof cnt);
	if(s[0] == '1'){
		dp[0][0][0][0] = 1;
		dp[0][0][1][1] = 1;
		dp[0][1][0][0] = 1;
		dp[0][1][1][1] = 1;

		cnt[0][0][0][0] = 2;
		cnt[0][0][1][1] = 3;
		cnt[0][1][0][0] = 2;
		cnt[0][1][1][1] = 3;
	} else {
		dp[0][0][0][1] = 1;
		dp[0][1][0][1] = 1;

		cnt[0][0][0][1] = 2;
		cnt[0][1][0][1] = 2;
	}
	int nb;
	for(int i = 0; i + 1 < n; i++){
		for(int j = 0; j < n; j++){
			for(int la = 0; la < 2; la++)
			for(int b = 0; b < 2; b++){
				for(int nx = 0; nx < 2; nx ++){
					if(b && nx > (s[i+1] - '0')) continue;
					if(b && nx == (s[i+1] - '0')) nb = 1;
					else nb = 0;
					(dp[i + 1][j + (nx ^ la ^ ss[i] ^ ss[i + 1])][nx][nb] += dp[i][j][la][b]) %= Mod;
					(cnt[i + 1][j + (nx ^ la ^ ss[i] ^ ss[i + 1])][nx][nb] += cnt[i][j][la][b]*2 + dp[i][j][la][b]*nx) %= Mod;	
				}
			}
		}
	}
	ll ans = 0;
	for(int la = 0; la < 2; la++) ans += cnt[n - 1][k][la][0];
	if(fl) for(int la = 0; la < 2; la++) ans += cnt[n - 1][k][la][1];
	//cerr << ans % Mod << '\n';
	return ans % Mod;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	cin >> t;
	for(int i = 0; i < n-1; i++) ss[i] = (t[i] == 'R');
	str A, B;
	cin >> A >> B;
	assert((int) B.size() == n);
	assert((int) A.size() == n);
	n --;
	ll res = Solve(B.substr(1));
	fl = 0;
	res -= Solve(A.substr(1));
	res += Mod;
	cout << res % Mod << '\n';
	return 0;
}

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