constint V = 1e4, E = 1e5; structedge { int u, v, w; booloperator<(const edge& rhs) const { return w < rhs.w; } } e[E], mxway[V]; map<int, int> g[V]; int lens[V]; int f[V]; intfind(int u){ return u == f[u] ? u : f[u] = find(f[u]); } voidaddedge(int u, int v, int w){ if (g[u].find(u) != g[u].end()) w = min(w, g[u][v]); g[u][v] = g[v][u] = w; } voideraedge(int u, int v){ g[u].erase(v), g[v].erase(u); }
voiddfs(int u, int father){ // for (pii x : g[u]) { for (IT it = g[u].begin(); it != g[u].end(); ++it) { pii x = *it; if (x.first == father) continue; if (x.second > mxway[u].w) mxway[x.first] = edge{u, x.first, x.second}; else mxway[x.first] = mxway[u]; dfs(x.first, u); } }
intklimitmst(int n, int m, int k){ int res = 0; // 求最小森林 sort(e + 1, e + m + 1); for (int i = 1; i <= n; ++i) f[i] = i, lens[i] = 2e9; for (int i = 1; i <= m; ++i) { if (e[i].u > e[i].v) swap(e[i].u, e[i].v); if (e[i].u == 1 || find(e[i].u) == find(e[i].v)) continue; addedge(e[i].u, e[i].v, e[i].w); f[find(e[i].u)] = find(e[i].v); res += e[i].w; } // 求最小k0限制生成 int k0 = 0; for (int i = 1; i <= m; ++i) { if (e[i].u == 1) { if (find(e[i].u) == find(e[i].v)) { lens[e[i].v] = min(lens[e[i].v], e[i].w); } else { addedge(e[i].u, e[i].v, e[i].w); f[find(e[i].u)] = find(e[i].v); res += e[i].w; k0++; } } } // 求最小k限制生成树 for (k0++; k0 <= k; k0++) { for (int i = 1; i <= n; ++i) mxway[i].w = -1; for (IT it = g[1].begin(); it != g[1].end(); ++it) dfs(it->first, 1); // for (pii x : g[1]) dfs(x.first, 1); int p = 2; for (int i = 3; i <= n; ++i) { if (lens[i] != 2e9 && lens[i] - mxway[i].w < lens[p] - mxway[p].w) p = i; } // cout << lens[p] << " " << mxway[p].w << endl; if (lens[p] - mxway[p].w >= 0) break; eraedge(mxway[p].u, mxway[p].v); addedge(1, p, lens[p]); res += lens[p] - mxway[p].w; lens[p] = 2e9; } return res; }
intread(){ int x; scanf("%d", &x); return x; }
intmain(){ // int n = read(), m = read(), k = read(); // for (int i = 1; i <= m; ++i) // e[i].u = read(), e[i].v = read(), e[i].w = read(); // cout << klimitmst(n, m, k) << endl; int n = 0, m = read(); map<string, int> id; id["Park"] = ++n; for (int i = 1; i <= m; ++i) { string s1, s2; cin >> s1 >> s2; if (id.find(s1) == id.end()) id[s1] = ++n; if (id.find(s2) == id.end()) id[s2] = ++n; e[i] = edge{id[s1], id[s2], read()}; } cout <<"Total miles driven: "<< klimitmst(n, m, read()) << endl; }
intmain(){ int n; while (scanf("%d", &n), n) { for (int i = 1; i <= n; i++) scanf("%d%d%d", x + i, y + i, h + i); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { double dx = x[i] - x[j], dy = y[i] - y[j], dh = h[i] - h[j]; A[i][j] = fabs(dh); B[i][j] = sqrt(dx * dx + dy * dy); } } double l = 0, r = 100; while (r - l > 1e-8) {// 二分 double mid = (l + r) / 2; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) W[i][j] = mid * B[i][j] - A[i][j];// 分数规划
int s = 1; for (int i = 1; i <= n; i++) mst[i] = 0, totree[i] = W[s][i]; // 距离 mst[s] = 1; double sum = 0; for (int t = 2; t <= n; t++) { int u = -1; for (int i = 1; i <= n; i++) if (mst[i] == 0 && (u == -1 || totree[u] < totree[i])) u = i; mst[u]=1; sum+=totree[u];// 取出最远的点，求最大生成树 for (int i = 1; i <= n; i++) if(mst[i]==0) totree[i] = max(totree[i], W[u][i]);//只有不在生成树中的点才被松弛 }// 生成树[?...sum] 与比值保持一致的单调性
sum > 0 ? r = mid : l = mid;// sum 大于0 则比值可以下降，则下移上界，反之上移下届 } printf("%.3f\n", l); } }
Easy Math Problem ### descirption One day, Touma Kazusa encountered a easy math problem. Given n and k, she need to calculate the following sum modulo \(1e9+7\). \[∑_{i=1}^n∑^n_{j=1}gcd(i,j)^klcm(i,j)\[gcd(i,j)∈prime\]\%(1e9+7) \] However, as a poor student, Kazusa obviously did not, so Touma Kazusa went to ask Kitahara Haruki. But Kitahara Haruki is too busy, in order to prove that he is a skilled man, so he threw this problem to you. Can you answer this easy math problem quickly?
input
There are multiple test cases.\(（T=5）\) The first line of the input contains an integer\(T\), indicating the number of test cases. For each test case:
There are only two positive integers n and k which are separated by spaces. \(1≤n≤1e10\)\(1≤k≤100\) ### output An integer representing your answer. ### sample input 1 10 2 ### sample output 2829 ### toturial \[
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^n i*j*gcd(i,j)^{k-1} gcd is prime
\\=&\sum_{d\in prime} \sum_{i=1}^n\sum_{j=1}^nijd^{k-1}[gcd(i,j)=d]
\\=&\sum_{d\in prime} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ijd^{k+1}[gcd(i,j)=1]
\\=&\sum_{d\in prime}d^{k+1} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij[gcd(i,j)=1]
\\=&\sum_{d\in prime}d^{k+1} \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j^2\phi(j)
\end{aligned}
\] 我们可以对n分块了，前面可以min25筛 \(\begin{aligned}f(j)=j^2\phi(j)\end{aligned}\)\(\begin{aligned}g(j)=j^2\end{aligned}\)\(\begin{aligned}f\ast g(j)=\sum_{i|j}i^2\phi(i)(\frac{j}{i})^2=j^2\sum_{i|j}\phi(i)=j^2(\phi\ast 1)(j)=j^3\end{aligned}\) 于是后面可以杜教筛 ### code
###descirption You are given an array \(a_1,a_2,...,a_n(∀i∈[1,n],1≤a_i≤n)\). Initially, each element of the array is unique.
Moreover, there are m instructions.
Each instruction is in one of the following two formats:
(1,pos),indicating to change the value of \(a_{pos}\) to \(a_{pos}+10,000,000\);
(2,r,k),indicating to ask the minimum value which is not equal to any \(a_i\) ( 1≤i≤r ) and not less than k.
Please print all results of the instructions in format 2.
###input The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.
In each test case, there are two integers n(1≤n≤100,000),m(1≤m≤100,000) in the first line, denoting the size of array a and the number of instructions.
In the second line, there are n distinct integers \(a_1,a_2,...,a_n (∀i∈[1,n],1≤a_i≤n)\),denoting the array. For the following m lines, each line is of format \((1,t_1) or (2,t_2,t_3)\). The parameters of each instruction are generated by such way :
For instructions in format 1 , we defined \(pos=t_1⊕LastAns\) . (It is promised that 1≤pos≤n)
For instructions in format 2 , we defined \(r=t_2⊕LastAns,k=t_3⊕LastAns\). (It is promised that 1≤r≤n,1≤k≤n )
(Note that ⊕ means the bitwise XOR operator. )
Before the first instruction of each test case, LastAns is equal to 0 .After each instruction in format 2, LastAns will be changed to the result of that instruction.
(∑n≤510,000,∑m≤510,000 )
###output For each instruction in format 2, output the answer in one line.
###hint note: After the generation procedure ,the instructions of the first test case are : 2 1 1, in format 2 and r=1 , k=1 2 3 3, in format 2 and r=3 , k=3 2 3 2, in format 2 and r=3 , k=2 2 3 1, in format 2 and r=3 , k=1 2 4 1, in format 2 and r=4 , k=1 2 5 1, in format 2 and r=5 , k=1 1 3 , in format 1 and pos=3 2 5 1, in format 2 and r=5 , k=1 2 5 2, in format 2 and r=5 , k=2
the instructions of the second test case are : 2 7 2, in format 2 and r=7 , k=2 1 5 , in format 1 and pos=5 2 7 2, in format 2 and r=7 , k=2 2 8 9, in format 2 and r=8 , k=9 1 8 , in format 1 and pos=8 2 8 9, in format 2 and r=8 , k=9
the instructions of the third test case are : 1 10 , in format 1 and pos=10 2 8 9 , in format 2 and r=8 , k=9 1 7 , in format 1 and pos=7 2 4 4 , in format 2 and r=4 , k=4 1 8 , in format 1 and pos=8 2 5 7 , in format 2 and r=5 , k=7 1 1 , in format 1 and pos=1 1 4 , in format 1 and pos=4 2 10 10, in format 2 and r=10 , k=10 1 2 , in format 1 and pos=2
###descirption Tom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is k and lexicographical order is the smallest. It's simple and he solved it with ease. But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom trouble any more. The constraints are: the number of occurrences of the ith letter from a to z (indexed from 1 to 26) must in \([L_i,R_i]\). Tom gets dizzy, so he asks you for help.
###input The input contains multiple test cases. Process until the end of file. Each test case starts with a single line containing a string \(S(|S|≤10^5)\)and an integer k(1≤k≤|S|). Then 26 lines follow, each line two numbers$ L_i,R_i(0≤L_i≤R_i≤|S|)$. It's guaranteed that S consists of only lowercase letters, and \(∑|S|≤3×10^5\).
###output Output the answer string. If it doesn't exist, output −1.