Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define mp make_pair
- #define f first
- #define s second
- #define pii pair<int, int>
- using namespace std;
- typedef long long ll;
- const int INF = (int) 1e9 + 7;
- const int MAXN = (int) 5e4 + 7;
- int tests;
- int n, banned;
- int dp[MAXN][1 << 4][2];
- int ways[MAXN][1 << 4][2];
- void add(int &x, int y) {
- x += y;
- if (x >= INF)
- x -= INF;
- }
- int main() {
- #ifdef LOCAL
- freopen("in", "r", stdin);
- #endif // LOCAL
- scanf("%d", &tests);
- while (tests--) {
- scanf("%d%d", &n, &banned);
- for (int mask = 0; mask < 16; mask++) {
- vector<int> arr;
- for (int i = 0; i < 4; i++)
- arr.pb((mask >> i) & 1);
- reverse(arr.begin(), arr.end());
- int sum = 0, ptr = 0;
- while (ptr < 4) {
- sum += arr[ptr] + 1;
- if (arr[ptr]) ptr += 2;
- else ptr++;
- }
- dp[4][mask][ptr == 4] += sum;
- ways[4][mask][ptr == 4]++;
- }
- for (int len = 4; len < n; len++) {
- for (int mask = 0; mask < 16; mask++) {
- for (int take = 0; take < 2; take++) {
- int sum = 0;
- for (int i = 0; i < 4; i++)
- sum += ((mask >> i) & 1) + 1;
- if (sum + 1 != banned) {
- // place 1
- int nmask = (mask & 7) << 1;
- if (take) {
- add(ways[len + 1][nmask][take], ways[len][mask][take]);
- add(dp[len + 1][nmask][take], dp[len][mask][take]);
- add(dp[len + 1][nmask][take], ways[len][mask][take]);
- } else {
- add(ways[len + 1][nmask][1], ways[len][mask][take]);
- add(dp[len + 1][nmask][1], dp[len][mask][take]);
- }
- }
- if (sum + 2 != banned) {
- // place 2
- int nmask = (mask & 7) << 1;
- ++nmask;
- if (take) {
- add(ways[len + 1][nmask][0], ways[len][mask][take]);
- add(dp[len + 1][nmask][0], dp[len][mask][take]);
- add(dp[len + 1][nmask][0], ways[len][mask][take]);
- add(dp[len + 1][nmask][0], ways[len][mask][take]);
- } else {
- add(ways[len + 1][nmask][1], ways[len][mask][take]);
- add(dp[len + 1][nmask][1], dp[len][mask][take]);
- }
- }
- }
- }
- }
- int ans = 0, all = 0;
- for (int mask = 0; mask < 16; mask++)
- for (int take = 0; take < 2; take++)
- add(ans, dp[n][mask][take]);
- printf("%d\n", ans);
- for (int i = 0; i <= n; i++)
- for (int mask = 0; mask < 16; mask++)
- for (int take = 0; take < 2; take++)
- dp[i][mask][take] = ways[i][mask][take] = 0;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement