結果

問題 No.2899 Taffy Permutation
コンテスト
ユーザー Mohammad Hussein
提出日時 2026-04-12 21:15:01
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,908 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,787 ms
コンパイル使用メモリ 163,748 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-12 21:15:10
合計ジャッジ時間 3,236 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 998244353;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 998244353;
        base = (base * base) % 998244353;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, 998244353 - 2);
}

int main() {
    int N;
    string S;
    cin >> N >> S;

    long long fact = 1;
    for (int i = 1; i <= N; i++) fact = (fact * i) % 998244353;

    int first_one = -1, last_zero = -1;
    for (int i = 0; i < N; i++) {
        if (S[i] == '1' && first_one == -1) first_one = i;
        if (S[i] == '0') last_zero = i;
    }

    // If no 0 exists after a 1, there are no constraints.
    if (first_one == -1 || last_zero == -1 || first_one > last_zero) {
        cout << fact << endl;
        return 0;
    }

    // Count 0s that have a 1 to their right
    int n0 = 0;
    for (int i = 0; i <= last_zero; i++) {
        if (S[i] == '0') n0++;
    }

    // Count 1s that have a 0 to their left
    int n1 = 0;
    for (int i = first_one; i < N; i++) {
        if (S[i] == '1') n1++;
    }

    // The number of ways to pick relative order for these n0 + n1 elements
    // is (n0 + n1)!, but only n0! * n1! of those are valid (where all n0 < all n1).
    // So we divide by (n0 + n1)C(n0).
    
    long long comb_den = 1;
    // Calculate (n0 + n1)! / (n0! * n1!)
    auto nCr = [&](int n, int r) {
        if (r < 0 || r > n) return 0LL;
        long long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num = (num * (n - i)) % 998244353;
            den = (den * (i + 1)) % 998244353;
        }
        return (num * modInverse(den)) % 998244353;
    };

    long long ans = (fact * modInverse(nCr(n0 + n1, n0))) % 998244353;
    cout << ans << endl;

    return 0;
}
0