結果
問題 | No.1214 Market |
ユーザー |
![]() |
提出日時 | 2020-08-30 16:58:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,557 ms / 2,000 ms |
コード長 | 10,828 bytes |
コンパイル時間 | 1,882 ms |
コンパイル使用メモリ | 131,096 KB |
最終ジャッジ日時 | 2025-01-14 00:22:04 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
//#pragma GCC optimize("Ofast")//#pragma GCC target("avx")//#undef LOCAL#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <complex>#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <string>#include <unordered_map>#include <unordered_set>#include <vector>using namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }template <class T> using V = vector<T>;template <class T> using VV = V<V<T>>;#include <unistd.h>struct Scanner {int fd = -1;char line[(1 << 15) + 1];size_t st = 0, ed = 0;void reread() {memmove(line, line + st, ed - st);ed -= st;st = 0;ed += ::read(fd, line + ed, (1 << 15) - ed);line[ed] = '\0';}bool succ() {while (true) {if (st == ed) {reread();if (st == ed) return false;}while (st != ed && isspace(line[st])) st++;if (st != ed) break;}if (ed - st <= 50) {bool sep = false;for (size_t i = st; i < ed; i++) {if (isspace(line[i])) {sep = true;break;}}if (!sep) reread();}return true;}template <class T, enable_if_t<is_same<T, string>::value, int> = 0>bool read_single(T& ref) {if (!succ()) return false;while (true) {size_t sz = 0;while (st + sz < ed && !isspace(line[st + sz])) sz++;ref.append(line + st, sz);st += sz;if (!sz || st != ed) break;reread();}return true;}template <class T, enable_if_t<is_integral<T>::value>* = nullptr>bool read_single(T& ref) {if (!succ()) return false;bool neg = false;if (line[st] == '-') {neg = true;st++;}ref = T(0);while (isdigit(line[st])) {ref = 10 * ref + (line[st++] & 0xf);}if (neg) ref = -ref;return true;}template <class T> bool read_single(V<T>& ref) {for (auto& d : ref) {if (!read_single(d)) return false;}return true;}void read() {}template <class H, class... T> void read(H& h, T&... t) {bool f = read_single(h);assert(f);read(t...);}int read_unsafe() { return 0; }template <class H, class... T> int read_unsafe(H& h, T&... t) {bool f = read_single(h);if (!f) return 0;return 1 + read_unsafe(t...);}Scanner(FILE* fp) : fd(fileno(fp)) {}};struct Printer {public:template <bool F = false> void write() {}template <bool F = false, class H, class... T>void write(const H& h, const T&... t) {if (F) write_single(' ');write_single(h);write<true>(t...);}template <class... T> void writeln(const T&... t) {write(t...);write_single('\n');}Printer(FILE* _fp) : fp(_fp) {}~Printer() { flush(); }private:static constexpr size_t SIZE = 1 << 15;FILE* fp;char line[SIZE], small[50];size_t pos = 0;void flush() {fwrite(line, 1, pos, fp);pos = 0;}void write_single(const char& val) {if (pos == SIZE) flush();line[pos++] = val;}template <class T, enable_if_t<is_integral<T>::value>* = nullptr>void write_single(T val) {if (pos > (1 << 15) - 50) flush();if (val == 0) {write_single('0');return;}if (val < 0) {write_single('-');val = -val; // todo min}size_t len = 0;while (val) {small[len++] = char(0x30 | (val % 10));val /= 10;}for (size_t i = 0; i < len; i++) {line[pos + i] = small[len - 1 - i];}pos += len;}void write_single(__int128 val) {if (pos > (1 << 15) - 50) flush();if (val == 0) {write_single('0');return;}if (val < 0) {write_single('-');val = -val; // todo min}size_t len = 0;while (val) {small[len++] = char(0x30 | (val % 10));val /= 10;}for (size_t i = 0; i < len; i++) {line[pos + i] = small[len - 1 - i];}pos += len;}void write_single(const string& s) {for (char c : s) write_single(c);}void write_single(const char* s) {size_t len = strlen(s);for (size_t i = 0; i < len; i++) write_single(s[i]);}template <class T> void write_single(const V<T>& val) {auto n = val.size();for (size_t i = 0; i < n; i++) {if (i) write_single(' ');write_single(val[i]);}}};template <uint MD> struct ModInt {using M = ModInt;static constexpr uint get_mod() { return MD; }const static M G;uint v;ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }M& set_v(uint _v) {v = (_v < MD) ? _v : _v - MD;return *this;}explicit operator bool() const { return v != 0; }M operator-() const { return M() - *this; }M operator+(const M& r) const { return M().set_v(v + r.v); }M operator-(const M& r) const { return M().set_v(v + MD - r.v); }M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }M operator/(const M& r) const { return *this * r.inv(); }M& operator+=(const M& r) { return *this = *this + r; }M& operator-=(const M& r) { return *this = *this - r; }M& operator*=(const M& r) { return *this = *this * r; }M& operator/=(const M& r) { return *this = *this / r; }bool operator==(const M& r) const { return v == r.v; }M pow(ll n) const {M x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}M inv() const { return pow(MD - 2); }friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }};// using Mint = ModInt<998244353>;// template<> const Mint Mint::G = Mint(3);template <class Mint>V<Mint> powTable(int n, Mint x) {V<Mint> table(n + 1);table[0] = Mint(1);for (int i = 1; i <= n; i++) {table[i] = table[i - 1] * x;}return table;}template<class Mint>struct Comb {int max_n;V<Mint> fact, ifact;Comb() {}Comb(int n) : max_n(n) {fact = ifact = V<Mint>(n + 1);fact[0] = Mint(1);for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;ifact[n] = fact[n].inv();for (int i = n; i >= 1; i--) ifact[i - 1] = ifact[i] * i;}Mint C(int n, int k) {if (n < k || n < 0) return Mint(0);assert(0 <= k && k <= n && n <= max_n);return fact[n] * ifact[k] * ifact[n - k];}// n個の区別出来ないボールをk個の箱に入れる入れ方Mint H(int n, int k) {if (n == 0 && k == 0) return Mint(1);return C(n + k - 1, n);}};using Mint = ModInt<TEN(9) + 7>;Comb<Mint> C(100);Scanner sc = Scanner(stdin);Printer pr = Printer(stdout);// (残った人数, lw, mid, up)Mint dp[42][42][2][42];Mint ndp[42][42][2][42];void succ() {for (int i = 0; i < 42; i++) {for (int j = 0; j < 42; j++) {for (int k = 0; k < 2; k++) {for (int l = 0; l < 42; l++) {dp[i][j][k][l] = ndp[i][j][k][l];ndp[i][j][k][l] = Mint(0);}}}}}int main() {int n, m, pri;sc.read(n, m, pri);using P = pair<int, int>;V<P> vs(m + 1);vs[0] = P(0, 0);for (int i = 1; i <= m; i++) {sc.read(vs[i].first, vs[i].second);}m++;sort(vs.begin(), vs.end());int bk = pri + 1;for (int i = m - 1; i >= 0; i--) {auto buf = vs[i].first;vs[i].first = bk - vs[i].first;bk = buf;}Mint ans = 0;for (int trg = 0; trg < m; trg++) {P tp = P(vs[trg].second, trg);succ(); succ();dp[n][0][0][0] = 1;int now_j = 0, now_l = 0;for (int ph = 0; ph < m; ph++) {P now_p = P(vs[ph].second, ph);// inc objectfor (int i = 0; i <= n; i++) {for (int j = 0; j < 42; j++) {for (int k = 0; k < 2; k++) {for (int l = 0; l < 42; l++) {if (!dp[i][j][k][l].v) continue;int nj = j;int nk = k;int nl = l;if (tp > now_p) nj++;if (tp == now_p) nk++;if (tp < now_p) nl++;ndp[i][nj][nk][nl] += dp[i][j][k][l];}}}}if (tp > now_p) now_j++;if (tp < now_p) now_l++;succ();Mint b = vs[ph].first;// inc humanfor (int i = 0; i <= n; i++) {for (int w = 0; w <= i; w++) {Mint freq = C.C(i, w) * b.pow(w);for (int j = 0; j <= now_j; j++) {for (int k = 0; k < 2; k++) {for (int l = 0; l <= now_l; l++) {if (!dp[i][j][k][l].v) continue;int z = w;int nl = l - min(l, z);z -= l - nl;int nk = k - min(k, z);z -= k - nk;int nj = j - min(j, z);z -= j - nj;ndp[i - w][nj][nk][nl] += dp[i][j][k][l] * freq;}}}}}succ();}Mint sum = 0;for (int j = 0; j < 42; j++) {for (int l = 0; l < 42; l++) {sum += dp[0][j][0][l];}};ans += sum * vs[trg].second;};ans /= Mint(pri + 1).pow(n);pr.writeln(ans.v);return 0;}