题解：CF2218G The 67th Iteration of "Counting is Fun"

lkjlkjlkj2012 · 2026-04-20 11:38:48 · 题解

思路

我们按 b_i 从小到大考虑。设第 i 秒结束后坐下的人数为 now_i。

我们只考虑 b_i\ge1，因为如果 b_i=0，那么一定 a_i=0。

如果它的邻居都是在 b_i 秒或更晚坐下，显然这个人不可能在第 b_i 秒坐下，输出 0。

反之，如果它的邻居有一个是前一秒坐下，另一个是前一秒及以后坐下，那么限制这个人坐下的因素是邻居没有坐下。只要 a_i\in[1,now_{i-1}] 即可。
否则，这个人的邻居在第 b_i-1 秒前至少有一个坐下，限制这个人坐下的因素一定是当前坐下的人数。则它的 a_i 需要保证第 b_i-1 秒时这个人不会坐下，第 b_i 秒时坐下，即 a_i\in[now_{i-2}+1,now_{i-1}] 即可。

代码

:::warning[真的要查看代码吗]

// Problem: G. The 67th Iteration of "Counting is Fun"
// Contest: Codeforces - Codeforces Round 1090 (Div. 4)
// URL: https://codeforces.com/contest/2218/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: lkjlkjlkj2012
// Time: 2026-04-20 10:26:04
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int   mod = 676767677;
int         t, n, m, b[200005], now[200005];
vector<int> c[200005];

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            cin >> b[i];
        for(int i = 1; i <= n; i++)
            c[b[i]].push_back(i);
        for(int i = 0; i < m; i++)
            now[i] = c[i].size() + (i == 0 ? 0 : now[i - 1]);
        int ans = 1;
        b[0] = b[n + 1] = 1e8;
        for(int i = 1; i < m; i++)
        {
            for(int x: c[i])
            {
                assert(b[x] == i);
                if(b[x - 1] >= b[x] && b[x + 1] >= b[x])
                {
                    ans = 0;
                    break;
                }
                if(b[x - 1] >= b[x] - 1 && b[x + 1] >= b[x] - 1)
                    (ans *= now[i - 1]) %= mod;
                else
                    (ans *= now[i - 1] - (i > 1 ? now[i - 2] : 0)) %= mod;
            }
        }
        cout << ans << "\n";
        for(int i = 0; i < m; i++)
            c[i].clear();
    }
    return 0;
}