Given ${N} $vertices, you can form a tree from these ${N} $vertices. If the tree has exactly three forks, we call this tree ${Y} $tree.
Now, given ${N} $vertices, please find out how many ${Y} $trees can be built from these ${N} $vertices?
###Input format:
The first line of input gives the number of vertices ${N} $.
${4 \le N \le 10^{18}}$
###Output format:
How many ${Y} $trees are built from these ${N} $vertices?, As a result, ${1e9+7} $is modeled. Output the results after taking the mold.
###Input example:
```in
4
```
###Output example:
```out
1
```
###Input example:
```in
6
```
###Output example:
```out
2
```
#include <iostream>
#include <stdio.h>
#define int long long
#define mod 1000000007
using namespace std;
int modpow(int a, int n)
{
if(n == 0) return 1;
if(n % 2){
return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
}
else{
return modpow((a*a)%mod, n/2) % mod;
}
}
int n;
int sum(int x)
{
x %= mod;
return x%mod * (x+1)%mod * modpow(2, mod-2) % mod;
}
int calc(int x)
{
int ret = sum(x/2) * 2 % mod;
if(x % 2 == 0) ret += mod - x/2%mod, ret %= mod;
return ret;
}
signed main()
{
cin >> n;
n--;
int ans = 0, k = n/3;
ans += calc(n-1) + mod - calc(n-k-1), ans %= mod;
ans += mod - sum(k) % mod, ans %= mod;
ans += k, ans %= mod;
cout << ans << endl;
return 0;
}Given a string ${Str} $. Please find the harmonic average in the non empty substring.
Definition of harmonic mean: the sum of different characters in each non empty substring divided by the number of non empty substrings.
For example, for the string ${ab} $, it has three substrings, namely ${a,b,ab} $, and the length is ${1,1,2} $. So the average is ${\ frac{1+1+2}{3}\approx1.33333} $
###Input format:
The first line of input gives a string ${Str} $, which consists of only lowercase letters.
${1 \le len(Str) \le 10^6}$
###Output format:
The harmonic average of the output non empty substring.
The error does not exceed ${10 ^ {- 5}}$
###Input example:
```in
ab
```
###Output example:
```out
1.3333333
```
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
string s;
cin >> s;
ll n = s.size();
double ans = n * (n + 1) *(n + 1) / 2 - n * (n + 1) * (2 * n + 1) / 6;
vector< int > pre(26, -1);
for (int i = 0; i < n; i++) {
if (pre[s[i] - 'a'] != -1) {
ans -= (n-i)*(pre[s[i]-'a'] + 1);
}
pre[s[i] - 'a'] = i;
}
printf("%.10f\n",ans*2/n/(n+1));
return 0;
}Give an array ${A} $from ${1 \sim N} $. Find the smallest permutation ${B} $, in dictionary order, from ${1 \sim N} $. If such an arrangement ${B} $does not exist, output ${- 1} $.
Permutation ${B} $is larger in dictionary order than permutation ${A} $
In the arrangement ${B} $, ${X} $is to the left of ${Y} $
###Input format:
The first line of input contains three integers ${N,X,Y} $.
The second line includes ${N} $integers ${a_1,a_2.....a_i...a_N} $, separated by spaces.
${2 \le N \le 2 \times 10^5}$
${1 \le X,Y \le N}$
${X \neq Y}$
###Output format:
Output qualified permutation ${B} $.
###Input example:
```in
5 1 2
5 4 3 2 1
```
###Output example:
```out
-1
```
###Input example:
```in
8 1 5
2 7 6 5 4 8 3 1
```
###Output example:
```out
2 7 6 8 1 3 4 5
```
#include <stdio.h>
#include <algorithm>
using namespace std;
int N, P, Q, A[200200], p, q;
int main()
{
scanf ("%d %d %d", &N, &P, &Q);
for (int i = 0; i < N; i++) scanf ("%d", &A[i]);
if (!next_permutation(A, A + N)){
puts("-1");
return 0;
}
for (int i = 0; i < N; i++){
if (A[i] == P) p = i;
if (A[i] == Q) q = i;
}
if (p < q){
for (int i = 0; i < N; i++) printf ("%d ", A[i]);
return 0;
}
int u = 0;
for (int i = q + 1; i < N; i++) u = max(u, A[i]);
if (Q > u){
int w = Q;
for (q--; q >= 0; q--){
if (w < A[q]) w = A[q];
else if (u < A[q] && A[q] < Q) u = A[q];
else break;
}
}
sort(A + q + 1, A + N);
reverse(A + q + 1, A + N);
if (!next_permutation(A, A + N)){
puts("-1");
return 0;
}
for (int i = 0; i < N; i++){
if (A[i] == P) p = i;
if (A[i] == Q) q = i;
}
if (p < q){
for (int i = 0; i < N; i++) printf ("%d ", A[i]);
return 0;
}
for (int i = 0; i < q; i++) printf ("%d ", A[i]);
for (int i = q + 1; i < p; i++) printf ("%d ", A[i]);
printf ("%d %d ", P, Q);
for (int i = p + 1; i < N; i++) printf ("%d ", A[i]);
return 0;
}Given a string ${Str} $, which is only composed of positive integer ${0 \sim 9} $, please find the maximum value of the multiple of three that can be composed of this string in the following ways.
*Select some numbers from the string ${Str} $and rearrange them.
*Leading zeros can exist in the number formed, but when the two numbers are the same, the more leading zeros, the greater the value. For example, ${0035} $and ${035} $both represent $, but ${0035} $has more leading zeros, so ${0035} $is larger.
###Input format:
Enter a string ${Str} $. In one line
${3 \le Str.size() \le 10^5}$
###Output format:
The output can form the maximum value of a multiple of three.
###Input example:
```in
666
```
###Output example:
```out
666
```
###Input example:
```in
4911815
```
###Output example:
```out
984111
```
#include<bits/stdc++.h>
using namespace std;
const int DIGITS = 10;
bool optimal(int i1, int j1, int i2, int j2)
{
if (i1 > j1)
swap(i1, j1);
if (i2 > j2)
swap(i2, j2);
if (i1 == -1)
{
if (i2 == -1)
return j1 < j2;
else
return true;
}
else
{
if (i2 == -1)
return false;
else if (j1 == j2)
return i1 < i2;
else
return j1 < j2;
}
}
int main()
{
string s;
cin >> s;
vector<int> d(DIGITS, 0);
int rem = 0;
for (int i = 0; i < (int)s.size(); i++)
d[s[i] - '0']++;
for (int i = 0; i < DIGITS; i++)
rem += i * d[i];
rem %= 3;
int ansi = -2;
int ansj = -2;
for (int i = -1; i < DIGITS; i++)
for (int j = i; j < DIGITS; j++)
{
if (i != -1 && d[i] == 0)
continue;
if (j != -1 && d[j] == 0)
continue;
if (i != -1 && i == j && d[i] < 2)
continue;
int remi = (i == -1) ? 0 : i % 3;
int remj = (j == -1) ? 0 : j % 3;
if ((9 + rem - remi - remj) % 3 == 0)
{
if (ansi == -2 && ansj == -2)
ansi = i, ansj = j;
else if (optimal(i, j, ansi, ansj))
ansi = i, ansj = j;
}
}
if (ansi != -1)
d[ansi]--;
if (ansj != -1)
d[ansj]--;
for (int i = DIGITS - 1; i >= 0; i--)
for (int j = 0; j < d[i]; j++)
printf("%d", i);
printf("\n");
return 0;
}Now give a sequence ${a =\{ A_1, a_2, a_3,..., a_i,.... a_n \} $. Now you can exchange any two numbers unlimited times, so that the value of ${\ sum_ {I = 1} ^ {I = n} {(- 1) ^ {I-1} \ times a_i = a_1-a_2 + a_3....... A_n} $is the largest. Find the maximum value.
###Input format:
On the first line, enter A positive integer ${n} $, indicating the size of the sequence ${A} $.
The next line gives ${N} $positive integers ${a_1, a_2... A_i.. A_N}$
${2 \le n\le 10^5}$
${1 \le a_i \le 1000}$
###Output format:
Output the maximum value of ${\ sum {I = 1} ^ {I = n} {(- 1) ^ {I-1}} \ times a_i} $.
###Input example:
```in
11
4 10 7 5 4 5 3 8 3 2 5
```
###Output example:
```out
10
```
###Input example:
```in
4
1 1 1 1
```
###Output example:
```out
0
```
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int ans = 0;
for (int i = 0; i < n; i++)
ans += a[i] * (i % 2 == 0 ? 1 : -1);
int minn = a[0];
for (int i = 0; i < n; i += 2)
minn = min(minn, a[i]);
int maxx = a[1];
for (int i = 1; i < n; i += 2)
maxx = max(maxx, a[i]);
ans = max(ans, ans - 2 * minn + 2 * maxx);
cout << ans << endl;
return 0;
}Now there are ${N} $peaches on the table. Niuniu wants to eat the peaches on the table in the following two ways:
Eat ${2^k} $peaches at one time. This operation cannot be performed if the peaches on the table do not exceed ${2^k} $. (each time this operation is selected, ${K} $can be any nonnegative integer).
From the kitchen, take ${2^m} $peaches and add them to the table. (each time this operation is selected, ${m} $can be any nonnegative integer).
Q: how many steps does it take to eat all the peaches on the table?
###Input format:
Enter the binary integer ${N} $(without leading zeros) in one line.
${1 \le N \le 2^{200000}}$
###Output format:
How many steps is it necessary to eat all the peaches on the table?
###Input example:
```in
1111
```
###Output example:
```out
2
```
###Input example:
```in
10001
```
###Output example:
```out
2
```
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
string s;cin >> s;
bool c = false;
int cnt = 0;
for (int i = s.size()-1; i >= 0; i--) {
if (c && s[i] == '1') {
s[i] = '0';
}
else if (c) {
c = false;
s[i] = '1';
i++;
}
else if (s[i] == '1' && i > 0 && s[i-1] == '1') {
c = true;
s[i] = '0';
cnt++;
}
}
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1') cnt++;
}
if (s[0] == '0') cnt++;
cout << cnt << endl;
return 0;
}