結果
問題 | No.243 出席番号(2) |
ユーザー |
![]() |
提出日時 | 2019-08-15 19:12:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,945 bytes |
コンパイル時間 | 586 ms |
コンパイル使用メモリ | 60,136 KB |
最終ジャッジ日時 | 2025-01-07 11:58:13 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 WA * 29 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:109:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 109 | scanf("%zu", &n); | ~~~~~^~~~~~~~~~~ main.cpp:114:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 114 | scanf("%zu", &a); | ~~~~~^~~~~~~~~~~
ソースコード
#include <cstdio>#include <cstdint>#include <vector>#include <algorithm>#include <numeric>#include <utility>template <typename Tp>Tp gcd(Tp a, Tp b, Tp& x, Tp& y) {x = Tp(0);y = Tp(1);for (Tp u = y, v = x; a;) {Tp q = b/a;std::swap(x -= q*u, u);std::swap(y -= q*v, v);std::swap(b -= q*a, a);}return b;}template <typename Tp>Tp modinv(Tp a, Tp mod) {Tp x, y;gcd(a, mod, x, y);x %= mod;if (x < 0) x += mod;return x;}template <typename Tp>Tp modadd(Tp a, Tp b, Tp mod) {a += b % mod;if (a < 0) a += mod;if (a >= mod) a -= mod;return a;}template <typename Tp>Tp modadd(std::initializer_list<Tp> const& adds, Tp mod) {Tp res = 0;for (auto const& add: adds) {res += add % mod;if (res < 0) res += mod;if (res >= mod) res -= mod;}return res;}template <typename Tp>Tp modsub(Tp a, Tp b, Tp mod) {a -= b % mod;if (a < 0) a += mod;if (a >= mod) a -= mod;return a;}template <typename Tp>Tp modmul(std::initializer_list<Tp> const& muls, Tp mod) {Tp res = 1;for (auto const& mul: muls) (res *= mul) %= mod;return res;}template <typename Tp>Tp modpow(Tp base, intmax_t iexp, Tp mod) {Tp res = 1;for (Tp dbl = base; iexp; iexp >>= 1) {if (iexp & 1) res = res * dbl % mod;dbl = dbl * dbl % mod;}return res;}class modfactorial {std::vector<intmax_t> fact, fact_inv;intmax_t mod;public:modfactorial(intmax_t N, intmax_t mod): mod(mod) {fact.resize(N+1);fact_inv.resize(N+1);fact[0] = 1;for (intmax_t i = 1; i <= N; ++i)fact[i] = fact[i-1] * i % mod;fact_inv[N] = modinv(fact[N], mod);for (intmax_t i = N; i--;)fact_inv[i] = fact_inv[i+1] * (i+1) % mod;}intmax_t operator ()(intmax_t k) const {return fact[k];}intmax_t inverse(intmax_t k) const {return fact_inv[k];}};constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }constexpr size_t operator ""_zu(unsigned long long n) { return n; }// constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }constexpr intmax_t mod = 1e9+7;int main() {size_t n;scanf("%zu", &n);std::vector<int> b(n);for (size_t i = 0; i < n; ++i) {size_t a;scanf("%zu", &a);if (a >= n) continue;++b[a];}std::vector<intmax_t> dp{1};for (size_t i = 0; i < n; ++i) {std::vector<intmax_t> tmp(i+2);for (size_t j = 0; j <= i; ++j) {(tmp[j] += dp[j]) %= mod;(tmp[j+1] += dp[j] * b[i]) %= mod;}dp = std::move(tmp);}modfactorial mf(n, mod);for (size_t i = 0; i <= n; ++i) {(dp[i] *= mf(n-i)) %= mod;}intmax_t res = 0;for (size_t i = 0; i <= n; ++i) {intmax_t cur = dp[i];if (!__builtin_parity(i)) cur = (mod-cur) % mod;(res += cur) %= mod;}printf("%jd\n", res);}