結果
問題 | No.243 出席番号(2) |
ユーザー | koyumeishi |
提出日時 | 2015-07-11 02:25:22 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 1,781 bytes |
コンパイル時間 | 737 ms |
コンパイル使用メモリ | 79,404 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-08 02:46:00 |
合計ジャッジ時間 | 2,251 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 10 ms
6,812 KB |
testcase_01 | AC | 10 ms
6,812 KB |
testcase_02 | AC | 10 ms
6,940 KB |
testcase_03 | AC | 11 ms
6,944 KB |
testcase_04 | AC | 10 ms
6,940 KB |
testcase_05 | AC | 10 ms
6,940 KB |
testcase_06 | AC | 10 ms
6,944 KB |
testcase_07 | AC | 10 ms
6,940 KB |
testcase_08 | AC | 14 ms
6,940 KB |
testcase_09 | AC | 13 ms
6,940 KB |
testcase_10 | AC | 14 ms
6,940 KB |
testcase_11 | AC | 14 ms
6,940 KB |
testcase_12 | AC | 14 ms
6,940 KB |
testcase_13 | AC | 20 ms
6,944 KB |
testcase_14 | AC | 20 ms
6,944 KB |
testcase_15 | AC | 20 ms
6,940 KB |
testcase_16 | AC | 19 ms
6,940 KB |
testcase_17 | AC | 19 ms
6,944 KB |
testcase_18 | AC | 27 ms
6,940 KB |
testcase_19 | AC | 26 ms
6,940 KB |
testcase_20 | AC | 29 ms
6,944 KB |
testcase_21 | AC | 29 ms
6,944 KB |
testcase_22 | AC | 28 ms
6,940 KB |
testcase_23 | AC | 38 ms
6,944 KB |
testcase_24 | AC | 37 ms
6,944 KB |
testcase_25 | AC | 37 ms
6,940 KB |
testcase_26 | AC | 37 ms
6,940 KB |
testcase_27 | AC | 37 ms
6,944 KB |
testcase_28 | AC | 9 ms
6,940 KB |
testcase_29 | AC | 10 ms
6,940 KB |
testcase_30 | AC | 10 ms
6,940 KB |
testcase_31 | AC | 10 ms
6,940 KB |
testcase_32 | AC | 9 ms
6,944 KB |
ソースコード
#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> #include <set> using namespace std; #define MOD 1000000007 //n! mod p table long long fact[400000+1]; void make_fact(long long p){ fact[0] = 1; for(int i=1; i<=400000; i++){ fact[i] = ((long long)fact[i-1]*i%p)%p; } } long long extgcd(long long a, long long b, long long &x, long long &y){ long long d=a; if(b!=0){ d = extgcd(b, a%b, y, x); y -= (a/b) * x; }else{ x = 1; y = 0; } return d; } long long mod_inverse(long long a, long long m){ long long x,y; extgcd(a,m,x,y); return (m+x%m)%m; } long long mod_fact(long long n, long long p, long long &e){ e = 0; if(n==0) return 1; long long res = mod_fact(n/p, p, e); e += n/p; if(n/p %2 != 0) return res * (p-fact[n%p]) %p; return res * fact[n%p]%p; } //nCk mod p long long mod_comb(long long n, long long k, long long p){ if(n<0 || k<0 || n<k) return 0; long long e1,e2,e3; long long a1 = mod_fact(n,p,e1); long long a2 = mod_fact(k,p,e2); long long a3 = mod_fact(n-k,p,e3); if(e1 > e2+e3) return 0; return a1 * mod_inverse(a2*a3 %p, p) %p; } int main(){ make_fact(MOD); int N; cin >> N; vector<int> cnt(5000, 0); vector<int> A(N); for(int i=0; i<N; i++){ cin >> A[i]; cnt[A[i]]++; } long long ans = 0; vector<long long> dp(N+1, 0); dp[0] = 1; for(int i=0; i<N; i++){ vector<long long> dp_ = dp; for(int j=0; j<=i; j++){ dp_[j+1] += cnt[i] * dp[j]; dp_[j+1] %= MOD; } swap(dp, dp_); } ans = fact[N]; for(int i=1; i<=N; i++){ //cerr << dp[i] << " "; ans -= dp[i] * (i%2==0?-1:+1) * fact[N-i] % MOD; ans = (ans%MOD + MOD)%MOD; } //cerr << endl; cout << ans << endl; return 0; }