D - Flip Cards

Solost

2023 年 03 月 02 日

185 次浏览

暂无评论

525字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F02%2Fimage.png)

## solution

这道题刚开始想的是所有的牌向上的那一面都不一样，然后就不知道怎么做了，后来读题是旁边的牌不一样就行。然后想的是这个鬼样子

```cpp
f[1][0] = f[1][1] = 0;
    int p1 = q[1].x, p2 = q[1].y;
    for(int i = 2; i <= n; i++){
        auto &t = q[i];
        if(p1 != t.x) f[i][0] = (f[i - 1][0] + 1) % p;
        if(p2 != t.x) f[i][0] = (f[i - 1][1] + 1) % p;
        if(p1 != t.y) f[i][1] = (f[i - 1][0] + 1) % p;
        if(p2 != t.y) f[i][1] = (f[i - 1][1] + 1) % p;
        p1 = t.x, p2 = t.y;
    }
    ll sum = (f[n][0] % p + f[n][1] % p) % p;
```

这个地方的问题是每增加一个数，多的不是1个，然是前f[i - 1]个，所以这里有问题。

正解应该是f数组，第一维度是第几张卡片，第二维度是正反面，那么整体意思就是f数组代表第i张卡片的时候组合出来的种类数，转移方程就是`f[i][0] = (a[i] != a[i - 1]) * f[i - 1][0],f[i][0] = (a[i] != b[i - 1]) * f[i - 1][1]`,如果此时卡片是正面，那么它可以由两种情况转移过来，第一种是和上一张卡片的正面不一样来转移，第二种是和上一张卡片的反面不一样转移，然后就是这张卡片的正面的情况，反面亦是如此。

```cpp
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, p = 998244353;
const int N = 2e5 + 10;

int qmi(int n, int k, int p){
    int res = 1 % p;
    while(k){
        if(k & 1) res = 1ll * res * n % p;
        n = 1ll * n * n % p;
        k >>= 1;
    }
    return res;
}
int f[N][2];
void solve(){
    int n;
    cin >> n;
    vector<PII> q(n + 10);
    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        q[i] = {x, y};
    }
    f[1][0] = f[1][1] = 0;
    int p1 = q[1].x, p2 = q[1].y;
    for(int i = 2; i <= n; i++){
        auto &t = q[i];
        if(p1 != t.x) f[i][0] = (f[i - 1][0] + 1) % p;
        if(p2 != t.x) f[i][0] = (f[i - 1][1] + 1) % p;
        if(p1 != t.y) f[i][1] = (f[i - 1][0] + 1) % p;
        if(p2 != t.y) f[i][1] = (f[i - 1][1] + 1) % p;
        p1 = t.x, p2 = t.y;
    }
    ll sum = (f[n][0] % p + f[n][1] % p) % p;
    cout << sum << endl;
}
int main(){
    IOS;
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 02 日