AcWing 3494. 国际象棋(lowbit)
原题链接
中等
作者:
半透明の微笑
,
2024-04-15 16:48:32
,
所有人可见
,
阅读 9
import java.io.*;
import java.util.*;
public class Main{
static int N = 110;
static int M = 1 << 7;
static int K = 21;
static long[][][][] f = new long[N][M][M][K];
static int MOD = (int)1e9 + 7;
static int n, m, k;
static int count(int x){
int res = 0;
while(x != 0){
//if((x & 1) == 1) res ++;
//x >>= 1;
x -= x & -x;//lowbit(x) = x & -x
res ++;
}
return res;
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
k = Integer.parseInt(s1[2]);
f[0][0][0][0] = 1;
for(int i = 1; i <= m; i ++){
for(int b = 0; b < 1 << n; b ++){
for(int a = 0; a < 1 << n; a ++){
if((a & b << 2) != 0 || (b & a << 2) != 0) continue;
for(int c = 0; c < 1 << n; c ++){
if((c & a << 2) != 0 || (a & c << 2) != 0) continue;
if((b & c << 1) != 0 || (c & b << 1) != 0) continue;
int t = count(b);
for(int j = t; j <= k; j ++){
f[i][a][b][j] = (f[i][a][b][j] + f[i - 1][c][a][j - t]) % MOD;
}
}
}
}
}
long res = 0;
for(int a = 0; a < 1 << n; a ++){
for(int b = 0; b < 1 << n; b ++){
res = (res + f[m][a][b][k]) % MOD;
}
}
System.out.println(res);
}
}