ABC 271 F - XOR on Grid Path
題意：
? 給出20 * 20的地圖，每個點上都有一個點權，保證為正整數，請問從(1, 1)走到(n, n)且路徑上所有點權異或和為0的路徑有多少條，
思路：
? 本題利用了meet in the mid的思想，因為是(1, 1)到(n, n)，所以一定會在某個中間的地方相遇，
? 走到某點(x, y)會有很多種路徑，以及很多個不同的異或和值，因為從(1, 1)走到(n, n)一共是2 * n步，
? 我們預處理從(1, 1)只向右下走，走到(x, y)，且步數為n的時候停止，并將異或和加入\(mp[x][y][val] ++\)，
? 然后再從(n, n)只向左上走，走到(x, y)的時候，如果此時的異或和有這樣的值存在\(mp[x][y]\)，就把方案數加上，
? 這樣做的時間復雜度是2 * C(20, 10)，還有一個map的log復雜度，（用umap可能被卡到O(n)，在CF慎用），
實作：
? \(map<int, int> [x][y]\)為走到(x, y)的時候，他的不同的值和其方案數，
int n;
int c[22][22];
map<int, int> mp[22][22];
int res = 0;
void dfs1(int x, int y, int step, int sum)
{
if (step == n)
{
mp[x][y][sum ^ c[x][y]]++; //最后一步
return;
}
if (x + 1 <= n)
dfs1(x + 1, y, step + 1, sum ^ c[x][y]);
if (y + 1 <= n)
dfs1(x, y + 1, step + 1, sum ^ c[x][y]);
}
void dfs2(int x, int y, int step, int sum)
{
if (step == n)
{
res += mp[x][y][sum];
return;
}
if (x - 1 >= 1)
dfs2(x - 1, y, step + 1, sum ^ c[x][y]);
if (y - 1 >= 1)
dfs2(x, y - 1, step + 1, sum ^ c[x][y]);
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> c[i][j];
dfs1(1, 1, 1, 0);
dfs2(n, n, 1, 0);
cout << res << '\n';
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511076.html
標籤：其他
下一篇：哈夫曼編碼