Submission #558374

#TimeUsernameProblemLanguageResultExecution timeMemory
558374Yazan_AlattarLjetopica (COI19_ljetopica)C++14
0 / 100
9 ms8436 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define F first #define S second #define pb push_back #define endl "\n" #define aint(x) x.begin(), x.end() const int M = 3007; const ll inf = 2e9; const ll mod = 1e9 + 7; const double pi = acos(-1); const double eps = 1e-6; const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0}; const int block = 320; ll n, k, p[M], ans, c[M][M]; string s, a, b; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> s >> a >> b; s = '#' + s; p[0] = 1; for(int i = 1; i <= n; ++i) p[i] = (p[i - 1] * 2) % mod; for(int i = 0; i <= n; ++i){ c[i][0] = 1; for(int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; } ll ans = (p[n] * c[n][k]) % mod; for(int i = 2; i <= n; ++i){ for(int j = 0; j <= k; ++j){ if(s[i - 1] == 'L' && j && j <= i - 1 && k - j <= n - i + 1){ ll add = (p[n - i] * c[n - i][k - j]) % mod; add = (add * c[i - 2][j - 1]) % mod; ans = (ans + add) % mod; // cout << i << " " << j << " " << add << endl; } else if(s[i - 1] == 'R' && j <= i - 2 && k - j <= n - i + 1){ ll add = (p[n - i] * c[n - i][k - j]) % mod; add = (add * c[i - 2][j]) % mod; ans = (ans + add) % mod; // cout << i << " " << j << " " << add << endl; } } } for(int i = 1; i < n; ++i){ if(s[i] == 'L') s[i] = 'R'; else s[i] = 'L'; } for(int i = 2; i <= n; ++i){ for(int j = 0; j <= k; ++j){ if(s[i - 1] == 'L' && j && j <= i - 1 && k - j <= n - i + 1){ ll add = (p[n - i] * c[n - i][k - j]) % mod; add = (add * c[i - 2][j - 1]) % mod; ans = (ans + add) % mod; // cout << i << " " << j << " " << add << endl; } else if(s[i - 1] == 'R' && j <= i - 2 && k - j <= n - i + 1){ ll add = (p[n - i] * c[n - i][k - j]) % mod; add = (add * c[i - 2][j]) % mod; ans = (ans + add) % mod; // cout << i << " " << j << " " << add << endl; } } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...