题目
I. Chinese chess
代码
Code
// <状压dp + 矩阵快速幂>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int mod = 20030214;
LL dp[2][1<<12]; // 滚动
vector<int> b[1<<12]; // b[i] 当前行的状态为i时, 上一行(下一行)的可行状态组成的列表
// 方阵 x 乘 y
vector<vector<int>> mul(vector<vector<int>> &x, vector<vector<int>> &y)
{
int n = x.size();
vector<vector<int>> res(n, vector<int>(n, 0));
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
for (int k = 0; k < n; k ++)
{
res[i][j] = (res[i][j] + 1ll * x[i][k] * y[k][j] % mod) % mod;
}
return res;
}
// 矩阵快速幂
vector<vector<int>> qpow(vector<vector<int>> x, int k)
{
int n = x.size();
vector<vector<int>> res(n, vector<int>(n, 0));
for (int i = 0; i < n; i ++) res[i][i] = 1; // 注意初始化单位阵
while (k)
{
if (k & 1) res = mul(res, x);
k >>= 1;
x = mul(x, x);
}
return res;
}
// 打印矩阵
void print(vector<vector<int>> &x)
{
cout << "---------------" << endl;
for (int i = 0; i < x.size(); i ++)
{
for (int j = 0; j < x[i].size(); j ++)
cout << x[i][j] << ' ';
cout << endl;
}
}
void solv()
{
int n, m;
cin >> n >> m;
n ++, m ++;
vector<int> a; // 单行合法状态
for (int i = 0; i < (1<<n); i ++) // 遍历单行所有状态, 找到合法状态
{
bool flag = true; // 初始合法
for (int j = 0; j < n; j ++) // 检查状态 i 的第 j 和 第j+1 位是否同时是 1(放置棋子)
{
bool x = i >> j & 1;
bool y = i >> (j + 1) & 1;
if (x && y) // 如果同时为1, 则非法
{
flag = false;
break;
}
}
if (flag) a.push_back(i); // 合法
}
dp[0][0] = 1;
int k = a.size(); // 方阵大小
vector<vector<int>> sq(k, vector<int>(k, 0)); // 零矩阵
for (int i = 0; i < a.size(); i ++)
{
for (int j = 0; j < a.size(); j ++)
if (!(a[i]&a[j])) // 相邻两行的状态组合 i j 合法 (即没有任何一位同时为 1)
{
sq[i][j] = 1;
b[a[i]].push_back(a[j]);
}
}
sq = qpow(sq, m+1);
cout << sq[0][0] << endl;
// // 以下为未使用矩阵快速幂加速dp时, 状态压缩dp的做法
// for (int _ = 1; _ <= m+1; _ ++)
// {
// int i = _ & 1;
// int ii = i ^ 1;
// for (auto x: a) // 遍历当前行状态
// {
// dp[i][x] = 0;
// for (auto y: b[x]) // 当前行状态可由上一行状态y转移过来
// {
// dp[i][x] = (dp[i][x] + dp[ii][y]) % mod;
// }
// }
// }
// LL ans = dp[(m+1)&1][0]; // 多计算一行, 则直接得到答案; 即 sum k: 0~(1<<n) dp[m&1][k]
// cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T --)
{
solv();
}
return 0;
}