結果
問題 | No.1261 数字集め |
ユーザー | 👑 hos.lyric |
提出日時 | 2020-10-16 22:56:10 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,044 ms / 8,000 ms |
コード長 | 4,623 bytes |
コンパイル時間 | 1,153 ms |
コンパイル使用メモリ | 104,252 KB |
実行使用メモリ | 30,612 KB |
最終ジャッジ日時 | 2023-09-28 09:36:23 |
合計ジャッジ時間 | 127,759 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,805 ms
30,480 KB |
testcase_01 | AC | 402 ms
20,240 KB |
testcase_02 | AC | 1,224 ms
26,012 KB |
testcase_03 | AC | 1,299 ms
26,128 KB |
testcase_04 | AC | 731 ms
22,084 KB |
testcase_05 | AC | 1,810 ms
29,744 KB |
testcase_06 | AC | 847 ms
23,028 KB |
testcase_07 | AC | 1,236 ms
26,524 KB |
testcase_08 | AC | 717 ms
21,700 KB |
testcase_09 | AC | 922 ms
23,440 KB |
testcase_10 | AC | 45 ms
15,592 KB |
testcase_11 | AC | 1,782 ms
29,532 KB |
testcase_12 | AC | 1,506 ms
28,020 KB |
testcase_13 | AC | 1,308 ms
26,588 KB |
testcase_14 | AC | 105 ms
16,016 KB |
testcase_15 | AC | 488 ms
20,772 KB |
testcase_16 | AC | 1,350 ms
26,452 KB |
testcase_17 | AC | 1,031 ms
24,348 KB |
testcase_18 | AC | 551 ms
20,764 KB |
testcase_19 | AC | 1,353 ms
26,108 KB |
testcase_20 | AC | 118 ms
16,540 KB |
testcase_21 | AC | 1,815 ms
30,328 KB |
testcase_22 | AC | 1,842 ms
30,524 KB |
testcase_23 | AC | 1,897 ms
30,564 KB |
testcase_24 | AC | 1,943 ms
30,372 KB |
testcase_25 | AC | 1,932 ms
30,336 KB |
testcase_26 | AC | 1,941 ms
30,352 KB |
testcase_27 | AC | 1,895 ms
30,340 KB |
testcase_28 | AC | 1,852 ms
30,276 KB |
testcase_29 | AC | 1,902 ms
30,272 KB |
testcase_30 | AC | 1,848 ms
30,492 KB |
testcase_31 | AC | 1,885 ms
30,492 KB |
testcase_32 | AC | 1,919 ms
30,316 KB |
testcase_33 | AC | 1,974 ms
30,460 KB |
testcase_34 | AC | 1,909 ms
30,348 KB |
testcase_35 | AC | 1,910 ms
30,480 KB |
testcase_36 | AC | 1,857 ms
30,264 KB |
testcase_37 | AC | 1,909 ms
30,476 KB |
testcase_38 | AC | 1,919 ms
30,268 KB |
testcase_39 | AC | 1,883 ms
30,412 KB |
testcase_40 | AC | 1,816 ms
30,504 KB |
testcase_41 | AC | 1,990 ms
30,464 KB |
testcase_42 | AC | 1,862 ms
30,560 KB |
testcase_43 | AC | 2,044 ms
30,316 KB |
testcase_44 | AC | 1,580 ms
28,664 KB |
testcase_45 | AC | 230 ms
18,132 KB |
testcase_46 | AC | 879 ms
22,292 KB |
testcase_47 | AC | 548 ms
20,236 KB |
testcase_48 | AC | 1,350 ms
26,508 KB |
testcase_49 | AC | 1,650 ms
28,504 KB |
testcase_50 | AC | 1,393 ms
27,048 KB |
testcase_51 | AC | 294 ms
18,336 KB |
testcase_52 | AC | 37 ms
15,480 KB |
testcase_53 | AC | 278 ms
18,324 KB |
testcase_54 | AC | 338 ms
18,912 KB |
testcase_55 | AC | 144 ms
16,740 KB |
testcase_56 | AC | 180 ms
17,320 KB |
testcase_57 | AC | 1,327 ms
25,928 KB |
testcase_58 | AC | 266 ms
18,092 KB |
testcase_59 | AC | 1,692 ms
28,948 KB |
testcase_60 | AC | 315 ms
18,908 KB |
testcase_61 | AC | 492 ms
20,192 KB |
testcase_62 | AC | 1,580 ms
27,408 KB |
testcase_63 | AC | 173 ms
17,152 KB |
testcase_64 | AC | 1,706 ms
30,148 KB |
testcase_65 | AC | 1,140 ms
24,856 KB |
testcase_66 | AC | 862 ms
23,140 KB |
testcase_67 | AC | 1,435 ms
27,380 KB |
testcase_68 | AC | 778 ms
22,756 KB |
testcase_69 | AC | 700 ms
22,552 KB |
testcase_70 | AC | 487 ms
21,100 KB |
testcase_71 | AC | 1,313 ms
26,928 KB |
testcase_72 | AC | 336 ms
19,184 KB |
testcase_73 | AC | 404 ms
19,888 KB |
testcase_74 | AC | 185 ms
17,264 KB |
testcase_75 | AC | 696 ms
22,080 KB |
testcase_76 | AC | 1,239 ms
25,916 KB |
testcase_77 | AC | 1,436 ms
27,728 KB |
testcase_78 | AC | 25 ms
15,336 KB |
testcase_79 | AC | 1,654 ms
28,168 KB |
testcase_80 | AC | 37 ms
15,736 KB |
testcase_81 | AC | 109 ms
16,224 KB |
testcase_82 | AC | 1,144 ms
25,224 KB |
testcase_83 | AC | 412 ms
19,844 KB |
testcase_84 | AC | 1,823 ms
30,408 KB |
testcase_85 | AC | 1,925 ms
30,480 KB |
testcase_86 | AC | 1,926 ms
30,528 KB |
testcase_87 | AC | 1,895 ms
30,544 KB |
testcase_88 | AC | 1,865 ms
30,492 KB |
testcase_89 | AC | 2,011 ms
30,472 KB |
testcase_90 | AC | 1,965 ms
30,520 KB |
testcase_91 | AC | 1,895 ms
30,460 KB |
testcase_92 | AC | 1,857 ms
30,480 KB |
testcase_93 | AC | 1,807 ms
30,612 KB |
ソースコード
#include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } template<int M_> struct ModInt { static constexpr int M = M_; int x; constexpr ModInt() : x(0) {} constexpr ModInt(long long x_) : x(x_ % M) { if (x < 0) x += M; } ModInt &operator+=(const ModInt &a) { x += a.x; if (x >= M) x -= M; return *this; } ModInt &operator-=(const ModInt &a) { x -= a.x; if (x < 0) x += M; return *this; } ModInt &operator*=(const ModInt &a) { x = static_cast<int>((static_cast<long long>(x) * a.x) % M); return *this; } ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); } ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); } ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); } ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); } ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); } ModInt operator-() const { return ModInt(-x); } ModInt pow(long long e) const { if (e < 0) return inv().pow(-e); ModInt x2 = x, xe = 1; for (; e; e >>= 1) { if (e & 1) xe *= x2; x2 *= x2; } return xe; } ModInt inv() const { int a = x, b = M, y = 1, z = 0, t; for (; ; ) { t = a / b; a -= t * b; if (a == 0) { assert(b == 1 || b == -1); return ModInt(b * z); } y -= t * z; t = b / a; b -= t * a; if (b == 0) { assert(a == 1 || a == -1); return ModInt(a * y); } z -= t * y; } } friend ModInt operator+(long long a, const ModInt &b) { return (ModInt(a) += b); } friend ModInt operator-(long long a, const ModInt &b) { return (ModInt(a) -= b); } friend ModInt operator*(long long a, const ModInt &b) { return (ModInt(a) *= b); } friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; } }; constexpr int MO = 1000000007; using Mint = ModInt<MO>; constexpr int LIM = 1'000'010; Mint inv[LIM], fac[LIM], invFac[LIM]; void prepare() { inv[1] = 1; for (int i = 2; i < LIM; ++i) { inv[i] = -(Mint::M / i) * inv[Mint::M % i]; } fac[0] = invFac[0] = 1; for (int i = 1; i < LIM; ++i) { fac[i] = fac[i - 1] * i; invFac[i] = invFac[i - 1] * inv[i]; } } Mint binom(Int n, Int k) { if (0 <= k && k <= n) { assert(n < LIM); return fac[n] * invFac[k] * invFac[n - k]; } else { return 0; } } Mint getInv(int d) { return (d < 0) ? -inv[-d] : inv[d]; } int N; Int M; vector<int> A; int Q; vector<int> X, Y; vector<Mint> AA; Mint ans; vector<int> goal; vector<Mint> sums; Mint calc(int u, int v) { const int a = A[u], b = A[v], c = A[N]; const Mint aa = AA[u], bb = AA[v], cc = AA[N]; Mint ret = -(aa * (b - c) + bb * (c - a) + cc * (a - b)); ret *= getInv(a - b); ret *= getInv(b - c); ret *= getInv(c - a); return ret; } void add(int u, int v) { if (v == N) { ans += sums[u]; goal[u] = 1; } else { const Mint here = calc(u, v); if (goal[v]) { ans += here; } sums[v] += here; } } int main() { prepare(); for (; ~scanf("%d%lld", &N, &M); ) { A.resize(N + 1); for (int u = 2; u <= N; ++u) { scanf("%d", &A[u]); --A[u]; } scanf("%d", &Q); X.resize(Q); Y.resize(Q); for (int q = 0; q < Q; ++q) { scanf("%d%d", &X[q], &Y[q]); } AA.assign(N + 1, 0); for (int u = 2; u <= N; ++u) { AA[u] = Mint(A[u]).pow((M - 3) + 2); } ans = 0; goal.assign(N + 1, 0); sums.assign(N + 1, 0); for (int u = 2; u <= N; ++u) { for (int v = 2 * u; v <= N; v += u) { add(u, v); } } printf("%d\n", ans.x); for (int q = 0; q < Q; ++q) { add(X[q], Y[q]); printf("%d\n", ans.x); } } return 0; }