結果

問題 No.243 出席番号(2)
ユーザー Pachicobue
提出日時 2019-02-07 18:51:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 686 bytes
コンパイル時間 497 ms
コンパイル使用メモリ 73,536 KB
最終ジャッジ日時 2025-01-06 20:50:02
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
using ll = long long;
constexpr ll MOD = 1000000007;
int main()
{
    int N;
    std::cin >> N;
    std::vector<int> dislike(N, 0);
    for (int i = 0, A; i < N; i++) {
        std::cin >> A;
        if (A < N) { dislike[A]++; }
    }
    std::vector<ll> dp(N + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = N - 1; j >= 0; j--) { (dp[j + 1] += dp[j] * dislike[i]) %= MOD; }
    }
    ll f = 1, ans = 0;
    for (int i = 0; i <= N; i++) {
        const ll S = dp[N - i] * f % MOD;
        (ans += ((N - i) % 2 == 0 ? S : MOD - S)) %= MOD, (f *= (i + 1)) %= MOD;
    }
    std::cout << ans << std::endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0