2024-12-20 22:20:54
发布于：广东
39阅读
0回复
0点赞
现在CF开了防火墙，所以暂时无法评测.
注意数据范围，地图不算很大，但是暴搜会运行 次，肯定会寄.
我们可以找一个中间线，记录 点至中间线、 点至中间线的所有状态，此时最多运行 次.
然后用哈希表查询中间点中所有匹配的状态数，相加就是结果了.
//O(2^40) -> 超时
//O(2^21+2^20) -> 可以
//应该不会卡map吧
#include <iostream>
#include <cstdio>
#include <unordered_map>
#define int long long
using namespace std;
int a[25][25];
int ct[25][25];
unordered_map <int, int> mp1[25][25], mp2[25][25];
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
if(n > m){//保证n<=m
swap(n, m);
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
cin >> a[j][i];
}
}
}else{
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
}
mp1[1][1][a[1][1]] = 1;
mp2[n][m][k ^ a[n][m]] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n - i + 1; j++){
if(i == 1 && j == 1) continue;
for(auto k:mp1[i - 1][j]) mp1[i][j][k.first ^ a[i][j]] += k.second;//记录11点至中间线的所有状态
for(auto k:mp1[i][j - 1]) mp1[i][j][k.first ^ a[i][j]] += k.second;
}
}
for(int i = n; i >= 1; i--){
for(int j = m; j >= n - i + 1; j--){
if(i == n && j == m) continue;
for(auto k:mp2[i + 1][j]) mp2[i][j][k.first ^ a[i][j]] += k.second;//记录nm点至中间线的所有状态
for(auto k:mp2[i][j + 1]) mp2[i][j][k.first ^ a[i][j]] += k.second;
}
}
int ct = 0;
for(int i = 1; i <= n; i++){
int j = n - i + 1;
for(auto k:mp1[i][j]) ct += mp2[i][j][k.first ^ a[i][j]] * k.second;//如果匹配，计算结果
}
cout << ct;
return 0;
}
有帮助，赞一个