結果
問題 | No.243 出席番号(2) |
ユーザー | kroton |
提出日時 | 2015-06-26 06:49:16 |
言語 | C++11 (gcc 13.3.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 800 bytes |
コンパイル時間 | 612 ms |
コンパイル使用メモリ | 62,188 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-07 17:40:45 |
合計ジャッジ時間 | 2,674 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 RE * 3 |
ソースコード
#include <iostream>#include <vector>using namespace std;typedef long long ll;const ll MOD = 1e9 + 7;ll solve(const vector<int>& dames){const int n = dames.size();vector<int> cnt(n, 0);for(int d : dames){++cnt[d];}vector<ll> dp(n + 1, 0);dp[0] = 1;for(int c : cnt){for(int s=n-1;s>=0;s--){dp[s+1] = (dp[s+1] + dp[s] * c % MOD) % MOD;}}vector<ll> perms(n + 1);perms[0] = 1;for(int i=1;i<=n;i++)perms[i] = perms[i-1] * i % MOD;ll res = 0;for(int i=0;i<=n;i++){ll tmp = dp[i] * perms[n-i] % MOD;if(i % 2 == 0) {res = (res + tmp) % MOD;} else {res = (res - tmp + MOD) % MOD;}}return res;}int main(){int N;cin >> N;vector<int> dames(N);for(int i=0;i<N;i++)cin >> dames[i];cout << solve(dames) << endl;return 0;}