結果
問題 | No.1261 数字集め |
ユーザー | torisasami4 |
提出日時 | 2020-10-17 01:31:21 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,979 ms / 8,000 ms |
コード長 | 5,615 bytes |
コンパイル時間 | 2,139 ms |
コンパイル使用メモリ | 176,224 KB |
実行使用メモリ | 65,880 KB |
最終ジャッジ日時 | 2023-09-28 10:40:49 |
合計ジャッジ時間 | 227,706 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,915 ms
65,404 KB |
testcase_01 | AC | 1,750 ms
55,276 KB |
testcase_02 | AC | 2,228 ms
61,384 KB |
testcase_03 | AC | 2,385 ms
61,316 KB |
testcase_04 | AC | 1,905 ms
57,460 KB |
testcase_05 | AC | 2,873 ms
65,140 KB |
testcase_06 | AC | 2,108 ms
58,224 KB |
testcase_07 | AC | 2,287 ms
61,744 KB |
testcase_08 | AC | 1,857 ms
56,712 KB |
testcase_09 | AC | 1,971 ms
58,520 KB |
testcase_10 | AC | 1,306 ms
50,376 KB |
testcase_11 | AC | 2,777 ms
64,956 KB |
testcase_12 | AC | 2,591 ms
63,328 KB |
testcase_13 | AC | 2,417 ms
61,808 KB |
testcase_14 | AC | 1,300 ms
51,184 KB |
testcase_15 | AC | 1,815 ms
55,920 KB |
testcase_16 | AC | 2,546 ms
61,712 KB |
testcase_17 | AC | 1,868 ms
59,556 KB |
testcase_18 | AC | 1,772 ms
55,932 KB |
testcase_19 | AC | 2,393 ms
61,536 KB |
testcase_20 | AC | 1,415 ms
51,612 KB |
testcase_21 | AC | 2,881 ms
65,668 KB |
testcase_22 | AC | 2,815 ms
65,744 KB |
testcase_23 | AC | 2,872 ms
65,560 KB |
testcase_24 | AC | 2,979 ms
65,860 KB |
testcase_25 | AC | 2,873 ms
65,628 KB |
testcase_26 | AC | 2,898 ms
65,636 KB |
testcase_27 | AC | 2,912 ms
65,672 KB |
testcase_28 | AC | 2,874 ms
65,624 KB |
testcase_29 | AC | 2,882 ms
65,544 KB |
testcase_30 | AC | 2,903 ms
65,628 KB |
testcase_31 | AC | 2,824 ms
65,740 KB |
testcase_32 | AC | 2,906 ms
65,616 KB |
testcase_33 | AC | 2,886 ms
65,564 KB |
testcase_34 | AC | 2,863 ms
65,560 KB |
testcase_35 | AC | 2,859 ms
65,604 KB |
testcase_36 | AC | 2,849 ms
65,880 KB |
testcase_37 | AC | 2,843 ms
65,816 KB |
testcase_38 | AC | 2,864 ms
65,676 KB |
testcase_39 | AC | 2,819 ms
65,468 KB |
testcase_40 | AC | 2,816 ms
65,760 KB |
testcase_41 | AC | 2,845 ms
65,608 KB |
testcase_42 | AC | 2,852 ms
65,532 KB |
testcase_43 | AC | 2,831 ms
65,672 KB |
testcase_44 | AC | 2,635 ms
63,636 KB |
testcase_45 | AC | 1,505 ms
53,024 KB |
testcase_46 | AC | 1,997 ms
57,428 KB |
testcase_47 | AC | 1,719 ms
55,188 KB |
testcase_48 | AC | 2,343 ms
61,516 KB |
testcase_49 | AC | 2,492 ms
63,492 KB |
testcase_50 | AC | 2,430 ms
62,072 KB |
testcase_51 | AC | 1,496 ms
53,532 KB |
testcase_52 | AC | 1,335 ms
50,168 KB |
testcase_53 | AC | 1,562 ms
53,488 KB |
testcase_54 | AC | 1,557 ms
54,132 KB |
testcase_55 | AC | 1,428 ms
52,064 KB |
testcase_56 | AC | 1,419 ms
52,436 KB |
testcase_57 | AC | 2,345 ms
61,144 KB |
testcase_58 | AC | 1,498 ms
53,348 KB |
testcase_59 | AC | 2,579 ms
64,116 KB |
testcase_60 | AC | 1,576 ms
53,796 KB |
testcase_61 | AC | 1,720 ms
55,652 KB |
testcase_62 | AC | 2,500 ms
62,604 KB |
testcase_63 | AC | 1,400 ms
52,288 KB |
testcase_64 | AC | 2,759 ms
65,148 KB |
testcase_65 | AC | 2,104 ms
60,012 KB |
testcase_66 | AC | 2,102 ms
58,516 KB |
testcase_67 | AC | 2,431 ms
62,576 KB |
testcase_68 | AC | 1,956 ms
57,884 KB |
testcase_69 | AC | 1,960 ms
57,692 KB |
testcase_70 | AC | 1,679 ms
56,188 KB |
testcase_71 | AC | 2,464 ms
62,060 KB |
testcase_72 | AC | 1,566 ms
54,328 KB |
testcase_73 | AC | 1,708 ms
55,120 KB |
testcase_74 | AC | 1,421 ms
52,508 KB |
testcase_75 | AC | 1,927 ms
57,128 KB |
testcase_76 | AC | 2,265 ms
61,204 KB |
testcase_77 | AC | 2,322 ms
62,836 KB |
testcase_78 | AC | 1,266 ms
50,020 KB |
testcase_79 | AC | 2,559 ms
63,364 KB |
testcase_80 | AC | 1,215 ms
50,104 KB |
testcase_81 | AC | 1,236 ms
51,672 KB |
testcase_82 | AC | 2,267 ms
60,260 KB |
testcase_83 | AC | 1,664 ms
54,596 KB |
testcase_84 | AC | 2,975 ms
65,620 KB |
testcase_85 | AC | 2,861 ms
65,688 KB |
testcase_86 | AC | 2,869 ms
65,528 KB |
testcase_87 | AC | 2,813 ms
65,672 KB |
testcase_88 | AC | 2,845 ms
65,612 KB |
testcase_89 | AC | 2,819 ms
65,684 KB |
testcase_90 | AC | 2,900 ms
65,600 KB |
testcase_91 | AC | 2,835 ms
65,740 KB |
testcase_92 | AC | 2,846 ms
65,604 KB |
testcase_93 | AC | 2,759 ms
65,628 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb(x) push_back(x) #define mp(a, b) make_pair(a, b) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define lscan(x) scanf("%I64d", &x) #define lprint(x) printf("%I64d", x) #define rep(i, n) for (ll i = 0; i < (n); i++) #define rep2(i, n) for (ll i = n - 1; i >= 0; i--) const ll mod = 1e9 + 7; ll gcd(ll a, ll b) { ll c = a % b; while (c != 0) { a = b; b = c; c = a % b; } return b; } long long extGCD(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } struct UnionFind { vector<ll> data; UnionFind(int sz) { data.assign(sz, -1); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return (false); if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return (true); } int find(int k) { if (data[k] < 0) return (k); return (data[k] = find(data[k])); } ll size(int k) { return (-data[find(k)]); } }; ll M = 1000000007; vector<ll> fac(2000011); //n!(mod M) vector<ll> ifac(2000011); //k!^{M-2} (mod M) ll mpow(ll x, ll n) { ll ans = 1; while (n != 0) { if (n & 1) ans = ans * x % M; x = x * x % M; n = n >> 1; } return ans; } ll mpow2(ll x, ll n, ll mod) { ll ans = 1; while (n != 0) { if (n & 1) ans = ans * x % mod; x = x * x % mod; n = n >> 1; } return ans; } void setcomb() { fac[0] = 1; ifac[0] = 1; for (ll i = 0; i < 2000010; i++) { fac[i + 1] = fac[i] * (i + 1) % M; // n!(mod M) } ifac[2000010] = mpow(fac[2000010], M - 2); for (ll i = 2000010; i > 0; i--) { ifac[i - 1] = ifac[i] * i % M; } } ll comb(ll a, ll b) { if (a == 0 && b == 0) return 1; if (a < b || a < 0) return 0; ll tmp = ifac[a - b] * ifac[b] % M; return tmp * fac[a] % M; } ll perm(ll a, ll b) { if (a == 0 && b == 0) return 1; if (a < b || a < 0) return 0; return fac[a] * ifac[a - b] % M; } long long modinv(long long a) { long long b = M, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= M; if (u < 0) u += M; return u; } ll modinv2(ll a, ll mod) { ll b = mod, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } template <int mod> struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt &operator+=(const ModInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt<mod>(t); return (is); } static int get_mod() { return mod; } }; using mint = ModInt<mod>; typedef vector<vector<mint>> Matrix; Matrix mul(Matrix a, Matrix b) { int i, j, k; mint t; int n = a.size(), m = b[0].size(), l = a[0].size(); Matrix c(n, vector<mint>(m)); for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { t = 0; for (k = 0; k < l; k++) t += a[i][k] * b[k][j]; c[i][j] = t; } } return c; } Matrix mat_pow(Matrix x, ll n) { ll k = x.size(); Matrix ans(k, vector<mint>(k, 0)); for (int i = 0; i < k; i++) ans[i][i] = 1; while (n != 0) { if (n & 1) ans = mul(ans, x); x = mul(x, x); n = n >> 1; } return ans; } mint inv[2000011], p[2000011]; mint calc(ll a, ll b, ll c){ ll cb = c - b, ca = c - a, ba = b - a; mint icb = inv[cb+(int)1e6], ica = inv[ca+(int)1e6], iba = inv[ba+(int)1e6]; mint pc = p[c+(int)1e6], pb = p[b+(int)1e6], pa = p[a+(int)1e6]; mint ans = pc * ica * icb; ans += pa * ica * iba; ans -= pb * icb * iba; return ans; } int main() { ll n, m; cin >> n >> m; ll a[n + 1]; rep(i, n - 1) scanf("%lld",&a[i + 2]), a[i + 2]--; mint ans = 0; mint sum[n + 1] = {}; int f[n + 1] = {}; rep(i, 2e6+10){ ll t = i - 1e6; if(t < 0) t += mod; if(t!=0) inv[i] = modinv(t), p[i] = mpow(t, m - 1); } for (ll i = 2; i < n; i++){ if(n%i==0){ ans += sum[i]; f[i]++; } for (ll j = i * 2; j < n; j += i) sum[j] += calc(a[i],a[j],a[n]); } cout << ans << endl; ll q; cin >> q; rep(i, q){ ll x, y; cin >> x >> y; if(y == n){ ans += sum[x]; f[x]++; } else{ if(f[y]) ans += calc(a[x],a[y],a[n]); sum[y] += calc(a[x],a[y],a[n]); } cout << ans << endl; } }