結果

問題 No.243 出席番号(2)
ユーザー tkmst201
提出日時 2020-11-13 10:44:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,834 bytes
コンパイル時間 2,099 ms
コンパイル使用メモリ 196,516 KB
最終ジャッジ日時 2025-01-15 22:18:27
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 RE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:105:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  105 |         REP(i, N) scanf("%d", &A[i]), ++cnt[A[i]];
      |                   ~~~~~^~~~~~~~~~~~~

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//
/*
P_i := i 君に出席番号 A_i が割り振られる事象
(\bigcup_{i=0}^N P_i)^c が答え(^c は補集合)
包除原理で求める
同じ A_i を持つような i から(2 つ以上)適当に選び b_1, b_2 , .., b_m とすると、
 \bigcap_{j=0}^m P_j = \emptyset
なので、同じ A_i を持つ人をまとめる
dp[i][j] :=
    A_i <= i を持つ人までで次の条件を満たす k の個数が j であるような選び方
    - 同じ A_k を持つような k は 1 つのみ
*/
template<int M>
struct ModInt {
public:
    using value_type = long long;
    
    ModInt(value_type val = 0) : val(val < 0 ? (M - (-val % M)) % M : val % M) {}
    
    explicit operator bool() const noexcept { return val; }
    bool operator ==(const ModInt & rhs) const noexcept { return val == rhs.val; }
    bool operator !=(const ModInt & rhs) const noexcept { return !(*this == rhs); }
    ModInt operator +() const noexcept { return ModInt(*this); }
    ModInt operator -() const noexcept { return ModInt(0) -= *this; }
    ModInt operator +(const ModInt & rhs) const noexcept { return ModInt(*this) += rhs; }
    ModInt operator -(const ModInt & rhs) const noexcept { return ModInt(*this) -= rhs; }
    ModInt operator *(const ModInt & rhs) const noexcept { return ModInt(*this) *= rhs; }
    ModInt operator /(const ModInt & rhs) const noexcept { return ModInt(*this) /= rhs; }
    
    ModInt & operator +=(const ModInt & rhs) noexcept {
        val += rhs.val;
        if (val >= M) val -= M;
        return *this;
    }
    ModInt & operator -=(const ModInt & rhs) noexcept {
        if (val < rhs.val) val += M;
        val -= rhs.val;
        return *this;
    }
    ModInt & operator *=(const ModInt & rhs) noexcept {
        val = val * rhs.val % M;
        return *this;
    }
    ModInt & operator /=(const ModInt & rhs) noexcept {
        *this *= rhs.inverse();
        return *this;
    }
    
    ModInt pow(value_type n) const {
        ModInt res = 1, x = val;
        if (n < 0) { x = x.inverse(); n = -n; }
        while (n) { if (n & 1) res *= x; x *= x; n >>= 1; }
        return res;
    }
    
    ModInt inverse() const {
        long long a = val, a1 = 1, a2 = 0, b = M, b1 = 0, b2 = 1;
        while (b > 0) {
            value_type q = a / b, r = a % b;
            value_type nb1 = a1 - q * b1, nb2 = a2 - q * b2;
            a = b; b = r;
            a1 = b1; b1 = nb1;
            a2 = b2; b2 = nb2;
        }
        assert(a == 1);
        return a1;
    }
    
    const value_type & get() const noexcept { return val; }
    static decltype(M) get_mod() noexcept { return M; }
    
    friend std::ostream & operator <<(std::ostream & os, const ModInt & rhs) { return os << rhs.val; }
    friend std::istream & operator >>(std::istream & is, ModInt & rhs) {
        value_type x;
        is >> x;
        rhs = ModInt(x);
        return is;
    }
private:
    value_type val;
};
using mint = ModInt<MOD>;
int main() {
    int N;
    cin >> N;
    vector<int> A(N), cnt(N);
    REP(i, N) scanf("%d", &A[i]), ++cnt[A[i]];
    
    /*
    dp[i][j] :=
    A_i <= i を持つ人までで次の条件を満たす k の個数が j であるような選び方
    - 同じ A_k を持つような k は 1 つのみ
    */
    vector<mint> dp(N + 1);
    dp[0] = 1;
    REP(i, N) for (int j = N - 1; j >= 0; --j) dp[j + 1] += dp[j] * cnt[i];
    
    vector<mint> fact(N + 1);
    fact[0] = 1;
    FOR(i, 1, N + 1) fact[i] = fact[i - 1] * i;
    
    mint ans = 0;
    REP(i, N + 1) {
        mint cur = dp[i] * fact[N - i];
        ans += cur * ((i & 1) ? -1 : 1);
    }
    
    cout << ans << endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0