結果
問題 | No.886 Direct |
ユーザー | hedwig100 |
提出日時 | 2022-03-20 18:13:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 870 ms / 4,000 ms |
コード長 | 5,441 bytes |
コンパイル時間 | 800 ms |
コンパイル使用メモリ | 76,928 KB |
実行使用メモリ | 73,600 KB |
最終ジャッジ日時 | 2024-10-07 04:34:24 |
合計ジャッジ時間 | 8,158 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 1 ms
5,248 KB |
testcase_12 | AC | 1 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 1 ms
5,248 KB |
testcase_16 | AC | 1 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 3 ms
5,248 KB |
testcase_19 | AC | 3 ms
5,248 KB |
testcase_20 | AC | 3 ms
5,248 KB |
testcase_21 | AC | 3 ms
5,248 KB |
testcase_22 | AC | 3 ms
5,248 KB |
testcase_23 | AC | 127 ms
20,992 KB |
testcase_24 | AC | 216 ms
30,976 KB |
testcase_25 | AC | 86 ms
16,640 KB |
testcase_26 | AC | 102 ms
18,048 KB |
testcase_27 | AC | 488 ms
51,328 KB |
testcase_28 | AC | 490 ms
51,328 KB |
testcase_29 | AC | 276 ms
26,624 KB |
testcase_30 | AC | 271 ms
26,752 KB |
testcase_31 | AC | 855 ms
73,472 KB |
testcase_32 | AC | 824 ms
73,600 KB |
testcase_33 | AC | 870 ms
73,600 KB |
testcase_34 | AC | 849 ms
73,600 KB |
testcase_35 | AC | 818 ms
73,472 KB |
コンパイルメッセージ
main.cpp: In function 'void zeta_set(std::vector<T>&)': main.cpp:40:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 40 | auto [d, sz] = min_pow2((int)f.size()); | ^ main.cpp: In function 'void mebius_set(std::vector<T>&)': main.cpp:52:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 52 | auto [d, sz] = min_pow2((int)f.size()); | ^
ソースコード
#include <iostream> #include <vector> // a <= b <=> a <= b // g[x] = \sum_{ i <= x } f[i] template <class T> void zeta(std::vector<T> &f) { int sz = (int)f.size(); for (int x = 1; x < sz; x++) { f[x] += f[x - 1]; } } template <class T> void mebius(std::vector<T> &f) { int sz = (int)f.size(); for (int x = sz - 1; x >= 1; x--) { f[x] -= f[x - 1]; } } // min_pow2 returns minimum power of 2 larger than x (x <= 2^i) // and i (pair{i,2^i}). // x must be more than 0 template <class T> std::pair<int, T> min_pow2(T x) { int i = 0; T ret = 1; while (x > ret) { i++; ret <<= 1; } return std::make_pair(i, ret); } // S <= T <=> S \subset T // g[T] = \sum_{ S \subset T } f[S] template <class R> void zeta_set(std::vector<R> &f) { auto [d, sz] = min_pow2((int)f.size()); f.resize(sz, (R)0); for (int i = 0; i < d; i++) { for (int T = 0; T < sz; T++) { if (T & (1 << i)) f[T] += f[T ^ (1 << i)]; } } } template <class R> void mebius_set(std::vector<R> &f) { auto [d, sz] = min_pow2((int)f.size()); f.resize(sz, (R)0); for (int i = 0; i < d; i++) { for (int T = 0; T < sz; T++) { if (T & (1 << i)) f[T] -= f[T ^ (1 << i)]; } } } // a <= b <=> b | a // g[x] = \sum_{ x | i } f[i] template <class T> void zeta_div(std::vector<T> &f) { int sz = (int)f.size(); for (int x = 1; x < sz; x++) { for (int i = 2 * x; i < sz; i += x) { f[x] += f[i]; } } } template <class T> void mebius_div(std::vector<T> &f) { int sz = (int)f.size(); for (int x = sz - 1; x >= 1; x--) { for (int i = 2 * x; i < sz; i += x) { f[x] -= f[i]; } } } int sample() { std::vector<int> f = {0, 1, 3, 24, 4, 2, 4, 4, 2, 1}; // a <= b printf("before\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); zeta_div(f); printf("transform\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); mebius_div(f); printf("return\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); // S \subset T printf("before\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); zeta_set(f); printf("transform\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); mebius_set(f); printf("return\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); // b | a printf("before\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); zeta_div(f); printf("transform\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); mebius_div(f); printf("return\n"); for (int i = 0; i < (int)f.size(); i++) { printf("%d ", f[i]); } printf("\n"); return 0; } /* https://yukicoder.me/problems/no/886 */ template <int Modulus> struct ModInt { long long x; ModInt(long long x = 0) : x((x % Modulus + Modulus) % Modulus) {} constexpr ModInt &operator+=(const ModInt a) { if ((x += a.x) >= Modulus) x -= Modulus; return *this; } constexpr ModInt &operator-=(const ModInt a) { if ((x += Modulus - a.x) >= Modulus) x -= Modulus; return *this; } constexpr ModInt &operator*=(const ModInt a) { (x *= a.x) %= Modulus; return *this; } constexpr ModInt &operator/=(const ModInt a) { return *this *= a.inverse(); } constexpr ModInt operator+(const ModInt a) const { return ModInt(*this) += a.x; } constexpr ModInt operator-(const ModInt a) const { return ModInt(*this) -= a.x; } constexpr ModInt operator*(const ModInt a) const { return ModInt(*this) *= a.x; } constexpr ModInt operator/(const ModInt a) const { return ModInt(*this) /= a.x; } friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt<Modulus> &a) { return os << a.x; } friend constexpr std::istream &operator>>(std::istream &is, ModInt<Modulus> &a) { return is >> a.x; } ModInt inverse() const { // x ^ (-1) long long a = x, b = Modulus, p = 1, q = 0; while (b) { long long d = a / b; a -= d * b; std::swap(a, b); p -= d * q; std::swap(p, q); } return ModInt(p); } ModInt pow(long long N) { // x ^ N ModInt a = 1; while (N) { if (N & 1) a *= *this; *this *= *this; N >>= 1; } return a; } }; using mint = ModInt<1000'000'007>; int main() { int H, W; std::cin >> H >> W; mint ans = mint(H) * mint(W - 1) + mint(W) * mint(H - 1); std::vector<mint> f(H + 1, 0), g(W + 1, 0); for (int i = 1; i <= H; i++) { f[i] = H - i; } for (int i = 1; i <= W; i++) { g[i] = W - i; } zeta_div(f); zeta_div(g); int sz = std::min((int)f.size(), (int)g.size()); std::vector<mint> h(sz); for (int i = 0; i < sz; i++) { h[i] = f[i] * g[i]; } mebius_div(h); ans += h[1] * 2; std::cout << ans << '\n'; }