結果

問題 No.3117 Reversible Tile
コンテスト
ユーザー chato
提出日時 2026-02-02 03:54:26
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 548 ms / 3,000 ms
コード長 3,119 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,867 ms
コンパイル使用メモリ 220,376 KB
実行使用メモリ 101,888 KB
最終ジャッジ日時 2026-02-02 03:54:38
合計ジャッジ時間 10,373 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
#define endl '\n'
using db = double;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x)
{
    if (x < 0)
    {
        x += P;
    }
    if (x >= P)
    {
        x -= P;
    }
    return x;
}
template <class T>
T power(T a, LL b)
{
    T res = 1;
    for (; b; b /= 2, a *= a)
    {
        if (b % 2)
        {
            res *= a;
        }
    }
    return res;
}
struct Z
{
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(P - x)); }
    Z inv() const
    {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs)
    {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs)
    {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs)
    {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs)
    {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs)
    {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs)
    {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a)
    {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) { return os << a.val(); }
};
const int N = 1e5 + 100;
vector<Z> fac(N + 1);
vector<Z> invfac(N + 1);
Z binom(int nn, int mm)
{
    if (nn < mm)
        return 0;
    return fac[nn] * invfac[nn - mm] * invfac[mm];
};
void init() // 记得初始化
{
    fac[0] = 1;
    for (int i = 1; i <= N; ++i)
        fac[i] = fac[i - 1] * i;
    invfac[N] = 1 / fac[N];
    for (int i = N - 1; i >= 0; --i)
        invfac[i] = invfac[i + 1] * (i + 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int dif = 0;
    for (int i = 1; i <= n + 1; ++i)
        dif += (a[i] != a[i - 1]);

    vector dp(m + 1, vector<Z>(n + 2));
    dp[0][dif] = 1;
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 0; j <= n + 1; ++j)
        {
            int j2 = n + 1 - j;
            if (j > 0 && j2 > 0)
                dp[i][j] += dp[i - 1][j] * j * j2;
            if (j >= 2)
                dp[i][j - 2] += dp[i - 1][j] * binom(j, 2);
            if (j2 >= 2)
                dp[i][j + 2] += dp[i - 1][j] * binom(j2, 2);
        }
    }
    cout << dp[m][0] << endl;
    return 0;
}
0