結果
問題 | No.1261 数字集め |
ユーザー |
![]() |
提出日時 | 2020-10-16 23:26:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,085 ms / 8,000 ms |
コード長 | 7,539 bytes |
コンパイル時間 | 1,481 ms |
コンパイル使用メモリ | 135,256 KB |
実行使用メモリ | 35,072 KB |
最終ジャッジ日時 | 2024-07-21 04:36:08 |
合計ジャッジ時間 | 37,257 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 94 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <utility>#include <tuple>#include <cstdint>#include <cstdio>#include <map>#include <queue>#include <set>#include <stack>#include <deque>#include <unordered_map>#include <unordered_set>#include <bitset>#include <cctype>#include <functional>#include <ctime>#include <fstream>#include <cmath>#include <limits>#include <chrono>#include <numeric>#include <type_traits>#include <iomanip>#include <float.h>#include <math.h>#include <cassert>#pragma warning (disable: 4996)using namespace std;using ll = long long;unsigned euclidean_gcd(unsigned a, unsigned b) {if (a < b) return euclidean_gcd(b, a);unsigned r;while ((r = a % b)) {a = b;b = r;}return b;}ll ll_gcd(ll a, ll b) {if (a < b) return ll_gcd(b, a);ll r;while ((r = a % b)) {a = b;b = r;}return b;}struct UnionFind {vector <ll> par;vector <ll> siz;UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {for (ll i = 0; i < sz_; ++i) par[i] = i;}void init(ll sz_) {par.resize(sz_);siz.assign(sz_, 1LL);for (ll i = 0; i < sz_; ++i) par[i] = i;}ll root(ll x) {while (par[x] != x) {x = par[x] = par[par[x]];}return x;}bool merge(ll x, ll y) {x = root(x);y = root(y);if (x == y) return false;if (siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;return true;}bool issame(ll x, ll y) {return root(x) == root(y);}ll size(ll x) {return siz[root(x)];}};long long modpow(long long a, long long n, long long mod) {if (n < 0)return 0;long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}long long modinv(long long a, long long mod) {return modpow(a, mod - 2, mod);}ll merge_cnt(vector<ll>& a) {int n = a.size();if (n <= 1) { return 0; }ll cnt = 0;vector<ll> b(a.begin(), a.begin() + n / 2);vector<ll> c(a.begin() + n / 2, a.end());cnt += merge_cnt(b);cnt += merge_cnt(c);int ai = 0, bi = 0, ci = 0;while (ai < n) {if (bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) {a[ai++] = b[bi++];}else {cnt += n / 2 - bi;a[ai++] = c[ci++];}}return cnt;}struct edge { ll to, cost; };typedef pair<ll, ll> P;struct graph {ll V;vector<vector<edge> > G;vector<ll> d;graph(ll n) {init(n);}void init(ll n) {V = n;G.resize(V);d.resize(V);for (int i = 0; i < V; i++) {d[i] = 2000000000000000000;}}void add_edge(ll s, ll t, ll cost) {edge e;e.to = t, e.cost = cost;G[s].push_back(e);}void dijkstra(ll s) {for (int i = 0; i < V; i++) {d[i] = 2000000000000000000;}d[s] = 0;priority_queue<P, vector<P>, greater<P> > que;que.push(P(0, s));while (!que.empty()) {P p = que.top(); que.pop();ll v = p.second;if (d[v] < p.first) continue;for (auto e : G[v]) {if (d[e.to] > d[v] + e.cost) {d[e.to] = d[v] + e.cost;que.push(P(d[e.to], e.to));}}}}};int main() {ll n,m;cin >> n >> m;m -= 3;vector<ll> z(n+1);for (int i = 0; i < n-1; i++) {cin >> z[i + 2];z[i + 2]--;}ll ans = 0;for (int i = 2; i < n; i++) {if (n % i != 0)continue;for (int j = 2; j < n/i; j++) {if (n % (i*j) != 0)continue;vector<ll> x(3);x[0] = z[n];x[1] = z[j*i];x[2] = z[i];sort(x.begin(), x.end());ll f = (modpow(x[2], m + 1, 1000000007) - modpow(x[1], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[1], 1000000007) % 1000000007 *x[1] % 1000000007;ll g= (modpow(x[2], m + 1, 1000000007) - modpow(x[0], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[0], 1000000007) % 1000000007 *x[0] % 1000000007;ans+=(f-g+1000000007) * modinv(x[1] - x[0], 1000000007) % 1000000007;}}ans %= 1000000007;ll q;cin >> q;set<ll> f;vector<vector<int>> d(n+1);for (int i = 0; i < q; i++) {cout << ans << endl;ll a, b;cin >> a >> b;d[b].push_back(a);if (b == n) {f.insert(a);for (int i = 2; i <= sqrt(a); i++) {if (a % i != 0)continue;if (i != sqrt(a)) {vector<ll> x(3);x[0] = z[n];x[1] = z[a/i];x[2] = z[a];sort(x.begin(), x.end());ll f = (modpow(x[2], m + 1, 1000000007) - modpow(x[1], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[1], 1000000007) %1000000007 * x[1] % 1000000007;ll g = (modpow(x[2], m + 1, 1000000007) - modpow(x[0], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[0], 1000000007) %1000000007 * x[0] % 1000000007;ans += (f - g + 1000000007) * modinv(x[1] - x[0], 1000000007) % 1000000007;}vector<ll> x(3);x[0] = z[n];x[1] = z[a];x[2] = z[i];sort(x.begin(), x.end());ll f = (modpow(x[2], m + 1, 1000000007) - modpow(x[1], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[1], 1000000007) %1000000007 * x[1] % 1000000007;ll g = (modpow(x[2], m + 1, 1000000007) - modpow(x[0], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[0], 1000000007) %1000000007 * x[0] % 1000000007;ans += (f - g + 1000000007) * modinv(x[1] - x[0], 1000000007) % 1000000007;}for (int i = 0; i < d[a].size(); i++) {vector<ll> x(3);x[0] = z[n];x[1] = z[a];x[2] = z[d[a][i]];sort(x.begin(), x.end());ll f = (modpow(x[2], m + 1, 1000000007) - modpow(x[1], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[1], 1000000007) %1000000007 * x[1] % 1000000007;ll g = (modpow(x[2], m + 1, 1000000007) - modpow(x[0], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[0], 1000000007) %1000000007 * x[0] % 1000000007;ans += (f - g + 1000000007) * modinv(x[1] - x[0], 1000000007) % 1000000007;}}else if (f.count(b)||n%b==0) {vector<ll> x(3);x[0] = z[n];x[1] = z[a];x[2] = z[b];sort(x.begin(), x.end());ll f = (modpow(x[2], m + 1, 1000000007) - modpow(x[1], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[1], 1000000007) % 1000000007 *x[1] % 1000000007;ll g = (modpow(x[2], m + 1, 1000000007) - modpow(x[0], m + 1, 1000000007) + 1000000007) * modinv(x[2] - x[0], 1000000007) % 1000000007 *x[0] % 1000000007;ans += (f - g + 1000000007) * modinv(x[1] - x[0], 1000000007) % 1000000007;}ans %= 1000000007;}cout << ans << endl;}