CF2005E2题解

· · 题解

我看不懂题解，但我会用 bitset！

考虑最简单的 \mathcal{O(nml)} 的算法。设 f_{i,j,k} 表示在 (i,j) 到 (n,m) 的子矩阵中第 k 轮时先手的胜负状态。显然有：

f_{i,j,k}=\left\{ \begin{aligned} &f_{i+1,j,k}|f_{i,j+1,k}|\neg f_{i+1,j+1,k+1} & & {b_{i,j}=a_k}\\ &f_{i+1,j,k}|f_{i,j+1,k} & & {\text{otherwise}}\\ \end{aligned} \right.

直接把 dp 数组的第三维压进 bitset 里。在 b_{i,j}\neq a_k 时转移是简单的；而在 b_{i,j}=a_k 时其实是对所有满足 a_k=b_{i,j} 的 k 进行转移。所以可以对每个不同的 a_i 预处理出所有 j 使得 a_i=a_j，压进一个 bitset g_{a_i} 里，转移方程：

f_{i,j}=f_{i+1,j}|f_{i,j+1}|(\neg(f_{i+1,j+1}>>1)\&g_{b_{i,j}})

时间复杂度 \mathcal{O(\frac{nml}{\omega})}，跑了不到 1 秒。

卡空间，需要滚动数组。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int MAX=1505,MOD=998244353;
int n,m,K;
int a[MAX],b[MAX][MAX];
bitset<MAX> f[2][MAX];
unordered_map<int,bitset<MAX>> bs;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin>>T;
    while(T--){
        cin>>K>>n>>m;
        for(int i=1;i<=m+1;i++){
            f[0][i].reset(); f[1][i].reset();
        }
        bs.clear();
        for(int i=1;i<=K;i++) cin>>a[i];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>b[i][j];
        for(int i=1;i<=K;i++) bs[a[i]][i]=1;
        for(int i=n;i>=1;i--){
            for(int j=m;j>=1;j--){
                f[i&1][j]=f[i&1^1][j]|f[i&1][j+1];
                if(bs.find(b[i][j])!=bs.end())
                    f[i&1][j]|=bs[b[i][j]]&(~(f[i&1^1][j+1]>>1));
            }
        }
        if(f[1][1][1]) cout<<"T\n";
        else cout<<"N\n";
    }
    return 0;
}