結果

問題 No.243 出席番号(2)
ユーザー Mao-beta
提出日時 2025-02-13 01:11:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 1,703 bytes
コンパイル時間 3,569 ms
コンパイル使用メモリ 276,828 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-13 01:11:45
合計ジャッジ時間 5,497 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MOD = 1000000007;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    // Count occurrences.
    // The Python code uses an array C of size 5000.
    const int MAXVAL = 5000;
    vector<int> C(MAXVAL, 0);
    for (int i = 0; i < N; i++){
        int x;
        cin >> x;
        // Increase count for number x.
        if(x < MAXVAL)
            C[x]++;
    }
    
    // dp[k]: number of ways to choose k "NG" items.
    // Initialize dp[0] = 1.
    vector<ll> dp(N+1, 0);
    dp[0] = 1;
    
    // For each i from 0 to N-1, update dp in reverse order.
    // This corresponds to:
    //   for i in range(N):
    //       for j in range(N-1, -1, -1):
    //           dp[j+1] += dp[j] * C[i] (mod MOD)
    for (int i = 0; i < N; i++){
        for (int j = N - 1; j >= 0; j--){
            dp[j+1] = (dp[j+1] + dp[j] * C[i]) % MOD;
        }
    }
    
    // Precompute factorials: fac[i] = i! mod MOD for i = 0..N.
    vector<ll> fac(N+1, 1);
    for (int i = 1; i <= N; i++){
        fac[i] = (fac[i-1] * i) % MOD;
    }
    
    // Calculate the answer.
    // In the Python code, the term (i%2*(-2)+1) equals 1 if i is even and -1 if i is odd.
    // Thus, we sum for i = 0..N: dp[i] * fac[N-i] * ( (i even) ? 1 : -1 ).
    ll ans = 0;
    for (int i = 0; i <= N; i++){
        ll term = (dp[i] * fac[N - i]) % MOD;
        if(i % 2 == 1) { // if odd, subtract the term (multiplying by MOD-1 gives -1 modulo MOD)
            term = (term * (MOD - 1)) % MOD;
        }
        ans = (ans + term) % MOD;
    }
    
    cout << ans % MOD << "\n";
    return 0;
}
0