WA 0pts,求助!
查看原帖
WA 0pts,求助!
1314900
LolaPeppa楼主2024/4/3 22:41
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 15, M = 1050, K = 110;
int n, k;
int cnt[M], state[M], num;
ll f[N][K][M];
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < (1 << n); i ++ )
    {
        int x = i;
        while (x)
        {
            if (x & 1) cnt[i] ++ ;
            x >>= 1;
        }
        if (((i<<1)|(i>>1))&i == 0) state[num ++ ] = i;
    }
    f[0][0][0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        for (int x = 0; x < num; x ++ )
            for (int y = 0; y < num; y ++ )
                if (((state[y]<<1)|(state[y]>>1)|state[y])&state[x] == 0)
                {
                    for (int j = 0; j <= k; j ++ )
                    {
                        if (j >= cnt[state[x]])
                            f[i][j][state[x]] += f[i - 1][j - cnt[state[x]]][state[y]];
                    }
                }
    }
    ll res = 0;
    for (int i = 0; i < num; i ++ ) res += f[n][k][state[i]];
    printf("%lld\n", res);
    return 0;
}
2024/4/3 22:41
加载中...