求助20pts,4号关注回报
查看原帖
求助20pts,4号关注回报
347589
Zelotz楼主2022/1/24 21:10
#include <bits/stdc++.h>
using namespace std;
#define srand srand(time(NULL))
#define random(x) rand() % (x)
#define il inline
#define ptc putchar
#define reg register
#define mp make_pair
typedef __int128 LL;
typedef long long ll;
typedef pair<int, int> PII;
namespace cyyh {
    template <typename T>
    il void read(T &x) {
        x = 0; T f = 1; char ch;
        while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar(); x *= f;
    }
    template <typename T>
    il void write(T x) {
        if (x < 0) ptc('-'), x = -x;
        if (x > 9) write(x / 10);
        ptc(x % 10 + '0');
    }
    template <typename T>
    il T lowbit(const T &x) {
        return x & -x;
    }
}
using namespace cyyh; 
#define int long long
int n, K, f[15][520][85], cnt[520];
void count_init() {
    for (int i = 1; i <= (1 << n); ++i) {
        int x = i;
        while (x) {
            if (x & 1) ++cnt[i];
            x >>= 1;
        }
    }
}
bool valid(int i, int x) {
	if (!i) return true;
    int q[15], idx = 0;
    memset(q, 0, sizeof q);
    while (x) {
        ++idx;
        if (x & 1) q[idx] = 1;
        x >>= 1;
    }
    for (int j = 1; j <= (n >> 1); ++j) swap(q[j], q[n - j + 1]);
    for (int j = 1; j < n; ++j) if (q[j] && q[j + 1]) return false;
    return true;
}
int ans = 0;
signed main() {
    read(n), read(K);
    count_init();
    for (int i = 0; i < (n << 1); ++i) if (valid(1, i) && cnt[i] <= K) f[1][i][cnt[i]] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            if (!valid(i, j)) continue;
            for (int k = 0; k < (1 << n); ++k) {
                if (!valid(i - 1, k)) continue;
            	for (int s = cnt[j]; s <= K; ++s) {
                    if ((j & k) || ((j << 1) & k) || ((j >> 1) & k)) continue;
                    f[i][j][s] += f[i - 1][k][s - cnt[j]];
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    	for (int j = 1; j < (1 << n); ++j) ans += f[i][j][K];
    write(ans);
    return 0;
}
2022/1/24 21:10
加载中...