传送门

题意

有 $n$ 张卡片，每张卡片有正反面，正反面各有一个数，（第 $i$ 张卡片正反面分别为 $a_{i,0}$ 和 $a_{i,1}$）。现在你可以随意切换卡牌的正反面，但每张卡牌的相对位置不动，问 $2^n$ 种切换正反的卡牌摆放方式有多少种是在上面的卡牌没有数字相同的。

题解

我们设 $f_{i,0}$ 表示第 $i$ 张卡片正面朝上时前 $i$ 张卡片的答案，$f_{i,1}$ 则表示第 $i$ 张卡片正面朝上时前 $i$ 张卡片的答案。最后的答案就是 $f_{n,0}+f_{n,1}$。

考虑转移：

• 如果 $a_{i,0} \neq a_{i-1,0}$ 则 $f_{i,0}=f_{i,0}+f_{i-1,0}$；
• 如果 $a_{i,0} \neq a_{i-1,1}$ 则 $f_{i,0}=f_{i,0}+f_{i-1,1}$；
• 如果 $a_{i,1} \neq a_{i-1,0}$ 则 $f_{i,1}=f_{i,1}+f_{i-1,0}$；
• 如果 $a_{i,1} \neq a_{i-1,1}$ 则 $f_{i,1}=f_{i,1}+f_{i-1,1}$；

代码:

#include <iostream>
#define md 998244353
using namespace std;
const int maxn = 200010;
int n;
long long f[maxn][2];
pair <int, int> p[maxn];
int main () {
  ios::sync_with_stdio (false), cin.tie (0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;
  f[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    if (p[i].first != p[i - 1].first) {
      f[i][0] = (f[i][0] + f[i - 1][0]) % md;
    }
    if (p[i].first != p[i - 1].second) {
      f[i][0] = (f[i][0] + f[i - 1][1]) % md;
    }
    if (p[i].second != p[i - 1].first) {
      f[i][1] = (f[i][1] + f[i - 1][0]) % md;
    }
    if (p[i].second != p[i - 1].second) {
      f[i][1] = (f[i][1] + f[i - 1][1]) % md;
    } // 注意要取模
  }
  cout << (f[n][0] + f[n][1]) % md;
  return 0;
}