P3977 [TJOI2015] 棋盘 题解

· · 题解

题意

题目中的所有编号都是从 0 开始！！！

有一个 n 行 m 列的棋盘，每个棋子的攻击范围是 3 行 p 列，棋子在中间一行，第 k 列，棋子不能互相攻击到，求摆放棋子的方案数。

思路

发现 m \le 6，所以考虑状压 dp。

先预处理出所有合法的状态 s。设 dp_{i,s} 表示第 i 行状态为 s 的方案数，则 dp_{i,s} = \sum\limits_{t\in V_s} dp_{i - 1, t}，这里集合 V_s 代表不会被状态 s 攻击到的状态集合，可以预处理出来或者 dp 时进行判断。

但是这样时间复杂度是 O(2^{2m}n) 的，会超时，考虑优化。

观察到 dp_{i,s} 只与 dp_{i - 1, t} 有关，所以考虑矩阵快速幂优化。

设 f_{s,t} 表示状态 t 是是否属于 V_s，则转移矩阵为：

\begin{bmatrix} dp_{i,0} & dp_{i,1} & \cdots & dp_{i,2^m-1} \end{bmatrix} \times \begin{bmatrix} f_{1, 1} & f_{2, 1} & \cdots & f_{2^m-1,1} \\ f_{1, 2} & f_{2, 2} & \cdots & f_{2^m-1,2} \\ \vdots \\ f_{1, 2^m-1} & f_{2, 2^m-1} & \cdots & f_{2^m-1,2^m-1} \\ \end{bmatrix} = \begin{bmatrix} dp_{i+1,0} & dp_{i+1,1} & \cdots & dp_{i+1,2^m-1} \end{bmatrix}

第一行可以预处理出来，状态 s 合法就为 1，否则为 0，所以只用转移 n - 1 次：

\begin{bmatrix} dp_{1,0} & dp_{1,1} & \cdots & dp_{1,2^m-1} \end{bmatrix} \times \begin{bmatrix} f_{1, 1} & f_{2, 1} & \cdots & f_{2^m-1,1} \\ f_{1, 2} & f_{2, 2} & \cdots & f_{2^m-1,2} \\ \vdots \\ f_{1, 2^m-1} & f_{2, 2^m-1} & \cdots & f_{2^m-1,2^m-1} \\ \end{bmatrix}^{n-1} = \begin{bmatrix} dp_{n,0} & dp_{n,1} & \cdots & dp_{n,2^m-1} \end{bmatrix}

最后答案为 \sum\limits_{s = 0}^{2^m-1} dp_{n,s}。

代码

struct node {
    ll a[80][80];
} zero, one, f, g;
ll N, a[20];
const ll mod = (1ll << 32);
vector <ll> v;

node mul(node x, node y) {
    node res = zero;
    for(ll i = 0; i <= N; i++) 
        for(ll j = 0; j <= N; j++)
            for(ll k = 0; k <= N; k++)
                res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
    return res;
}
node pw(node x, ll y) {
    node res = one;
    while(y) {
        if(y & 1) res = mul(res, x);
        x = mul(x, x), y >>= 1;
    }
    return res;
}
signed main() {
    ll n = rd(), m = rd(), p = rd(), k = rd();
    N = (1 << m) - 1;
    for(ll i = 1; i <= 3; i++) 
        for(ll j = 0; j < p; j++) a[i] |= rd() * (1ll << j);
    for(ll s = 0; s <= N; s++) {
        one.a[s][s] = 1;
        ll flag = 1;
        for(ll i = 0; i < m; i++) {
            if(!((1 << i) & s)) continue;
            ll t = s;
            if(i < k) t <<= k - i;
            if(i > k) t >>= i - k;
            if((t & a[2]) != (1 << k)) flag = 0, i = m;
        }
        if(flag) v.push_back(s), g.a[1][s] = 1;  
    }
    for(ll s : v) for(ll t : v) {
        ll flag = 1;
        for(ll i = 0; i < m; i++) {
            if(!((1 << i) & t)) continue;
            ll tt = s;
            if(i < k) tt <<= k - i;
            if(i > k) tt >>= i - k;
            if(tt & a[1]) flag = 0, i = m;
        }
        for(ll i = 0; i < m; i++) {
            if(!((1 << i) & s)) continue;
            ll tt = t;
            if(i < k) tt <<= k - i;
            if(i > k) tt >>= i - k;
            if(tt & a[3]) flag = 0, i = m;
        }
        if(flag) f.a[t][s] = 1;
    }
    node res = mul(g, pw(f, n - 1));
    ll ans = 0;
    for(ll i = 0; i <= N; i++) ans = (ans + res.a[1][i]) % mod;
    cout << (ans + mod) % mod;
    return 0;
}