解法
半分全列挙. 最短ルートで移動したとき,右上から左下の対角線 \(l\) を一度だけ通る. \(l\) で正方形を 2分割して,それぞれで計算した結果をつなげる.
左上から \(l\) への移動方法は,雑に見積もって \(2^{n}\)通り. 点 \(\,(x,y\,)\) に居るとき,経路の xor としてあり得る値全体を \(dp_{x,y}\) とおく.経路として,\(\,(x,y)\,\) 自身を含む.
注意
matrx を回転させたとき,index が変わる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
auto f = [&](const vvll &a) -> vvll {
vvvll dp(n, vvll(n)); // (x,y) 含む
dp[0][0].push_back(a[0][0]);
rep(x,n) rep(y,n) if(x+y < n-1){
for(auto i: dp[x][y]){
if(x+1 < n) dp[x+1][y].push_back(i^a[x+1][y]);
if(y+1 < n) dp[x][y+1].push_back(i^a[x][y+1]);
}
}
vvll res(n);
rep(x,n){
ll y = n-1-x;
res[x] = dp[x][y];
}
return res;
};
vvll a(n, vll(n)); cinvv(a);
vvll b(n, vll(n));
rep(x,n) rep(y,n) b[x][y] = a[n-1-x][n-1-y];
vvll ra = f(a);
vvll rb = f(b);
ll ans = 0;
rep(x,n){
ll y = n-1-x;
for(auto v:rb[n-1-x]) mpb[v]++; // rem: rb[n-1-x]
ll cb = mpb[v^a[x][y]];
ans += ca*cb;
}
}
cout << ans << endl;
return 0;
}