Codeforces Round 838 (Div. 2)题解

A. Divide and Conquer

题意：

思路：

代码：

B. Make Array Good

题意：

思路：

代码：

C. Binary Strings are Fun

题意：

思路：

代码：

D. GCD Queries

题意：

思路：

代码：

E. Tree Sum（枚举，贡献）

题意：

思路：

代码：

A. Divide and Conquer

An array b is good if the sum of elements of b is even.

You are given an array a consisting of n positive integers. In one operation, you can select an index i and change ai:=⌊ai2⌋. ††

Find the minimum number of operations (possibly 00) needed to make a good. It can be proven that it is always possible to make a good.

Input

Each test contains multiple test cases. The first line contains a single integer t (1≤t≤1000) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤50) — the length of the array a.

The second line of each test case contains n space-separated integers a1,a2,…,an (1≤ai≤106) — representing the array a.

Do note that the sum of n over all test cases is not bounded.

Output

For each test case, output the minimum number of operations needed to make a good.

Example

input

4

4

1 1 1 1

2

7 4

3

1 2 4

1

15

output

题意：

给一个数组，每次将一个数整除2，最少几次操作后，数组之和为偶数

思路：

计算每个元素变奇偶需要的次数，取最少次数

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<'='<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int INF=0x3f3f3f3f;#define int long longvoid solve(){int n;cin>>n;vector<int>a(n+1);int sum=0;int ans=INT_MAX;int x;for(int i=1;i<=n;i++){cin>>x;sum+=x;int cnt=0;if(x%2==0){while(x%2==0){cnt++;x/=2;}}else{while(x%2==1){cnt++;x/=2;}}ans=min(ans,cnt);}if(sum%2==0)cout<<0<<endl;else cout<<ans<<endl;return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

B. Make Array Good

An array b of m positive integers is good if for all pairs iand j (1≤i,j≤m, max(bi,bj) is divisible by min(bi,bj)

You are given an array a of npositive integers. You can perform the following operation:

Select an index i (1≤i≤n1 and an integer x (0≤x≤ai) and add xto ai, in other words, ai:=ai+x
After this operation, ai≤1018 should be satisfied.

You have to construct a sequence of at most n operations that will make a good. It can be proven that under the constraints of the problem, such a sequence of operations always exists.

Input

Each test contains multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤105) — the length of the array a.

The second line of each test case contains n space-separated integers a1,a2,…,an (1≤ai≤109) — representing the array a.

It is guaranteed that the sum of n over all test cases does not exceed 105105.

Output

For each test, output a single integer p (0≤p≤n) — denoting the number of operations in your solution.

In each of the following p lines, output two space-separated integers — i and x.

You do not need to minimize the number of operations. It can be proven that a solution always exists.

Example

input

4

2 3 5 5

2

4 8

5

3 4 343 5 6

3

31 5 17

output

题意：

给一个数组，每次将一个数加上不超过自己的数，最少几次操作后，任意两个数具有整除关系

思路：

对数组排序，把每个数变成上一个数的倍数，map储存答案

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<'='<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int INF=0x3f3f3f3f;#define int long longvoid solve(){int n;cin>>n;vector<int>a(n+1),b(n+1);for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];sort(b.begin()+1,b.end());b.erase(unique(b.begin()+1,b.end()),b.end());map<int,int>ans;ans[b[1]]=0;for(int i=2;i<b.size();i++){if(b[i]<=b[i-1]){ans[b[i]]=b[i-1]-b[i];b[i]=b[i-1];continue;}int tmp=b[i]%b[i-1];ans[b[i]]=b[i-1]-tmp;b[i]+=ans[b[i]];}cout<<n<<endl;for(int i=1;i<=n;i++){cout<<i<<' '<<ans[a[i]]<<endl;}return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

C. Binary Strings are Fun

A binary string†† b of odd length m is good if bi is the median‡‡ of b[1,i]§ for all odd indices i (1≤i≤m.

For a binary string aof length k, a binary string b of length 2k−1 is an extension of a if b2i−1=ai for all i such that 1≤i≤k. For example, 1001011 and 1101001 are extensions of the string 1001. String x=1011011 is not an extension of string y=1001 because x3≠y2. Note that there are 2k−1 different extensions of a.

You are given a binary string s of length n. Find the sum of the number of good extensions over all prefixes of s. In other words, find ∑ni=1f(s[1,i]), where f(x) gives number of good extensions of string x. Since the answer can be quite large, you only need to find it modulo 998244353.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤2⋅105), where n is the length of the binary string s.

The second line of each test case contains the binary string s of length n.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, print the answer modulo 998244353998244353.

Example

input

6

1

1

1

0

2

11

3

010

9

101101111

37

1011011111011010000011011111111011111

output

题意：

给一个01串，问这个串的前缀的好串总数有多少

一个长为k的串的好串，定义为往相邻两位间插入k-1个01，新串每个奇数位置的前缀里，都有超过一半的这一位数

思路：

对于每个前缀串，如果末位连续数字只有一个，只能有一种填法，否则每个连续数字前都可以任意填，1+2+4+8=2^cnt-1，累加即可

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<'='<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int INF=0x3f3f3f3f;#define int long longvoid solve(){int n;cin>>n;string s;int mod=998244353;cin>>s;int ans=0;int cnt=2;for(int i=1;i<n;i++){if(s[i]==s[i-1]){cnt=(cnt*2)%mod;}else{ans=(ans+cnt-1)%mod;cnt=2;}}ans=(ans+cnt-1)%mod;cout<<ans<<endl;return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

D. GCD Queries

This is an interactive problem.

There is a secret permutation p of [0,1,2,…,n−1]. Your task is to find 22 indices x and y (1≤x,y≤n, possibly x=y) such that px=0 or py=0. In order to find it, you are allowed to ask at most 2n queries.

In one query, you give two integers i and j (1≤i,j≤n, i≠j) and receive the value of gcd(pi,pj).

Note that the permutation pis fixed before any queries are made and does not depend on the queries.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104. The description of the test cases follows.

The first line of each test case contains a single integer n (2≤n≤2⋅104).

After reading the integer n for each test case, you should begin the interaction.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅104.

Interaction

The interaction for each test case begins by reading the integer n.

To make a query, output "? i j" (1≤i,j≤n, i≠j) without quotes. Afterwards, you should read a single integer — the answer to your query gcd(pi,pj). You can make at most 2nsuch queries in each test case.

If you want to print the answer, output "! x y" (1≤x,y≤n) without quotes. After doing that, read 11 or −1−1. If px=0 or py=0, you'll receive 11, otherwise you'll receive −1−1. If you receive −1−1, your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Example

input

2
211
5241

output

? 1 2! 1 2? 1 2? 2 3! 3 3

题意：

有一个0 - n-1的排列，询问不超过2n次两数的gcd，输出x y，有一个是0

思路：

由于是排列，每个数不相等，假设出现了0，还有x和y（x<y），他们最大的gcd是gcd(0,y)=y，我们维护x和y，每次插入一个数，查询和x、y的gcd并保留gcd最大的两个数，一旦出现0，保证0一直处于x和y中

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<'='<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int INF=0x3f3f3f3f;#define int long longint Get(int a,int b){cout<<"? "<<a<<' '<<b<<endl;cout.flush();int x;cin>>x;return x;
}
void push(int a,int b){cout<<"! "<<a<<' '<<b<<endl;cout.flush();int x;cin>>x;
}
void solve(){int n;cin>>n;int x=1,y=2;int now=Get(1,2);for(int i=3;i<=n;i++){int t=Get(x,i),tt=Get(y,i);if(t>now){now=t;y=i;}if(tt>now){now=tt;x=i;}}push(x,y);return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

E. Tree Sum（枚举，贡献）

Let us call an edge-weighted tree with n vertices numbered from 1 to n good if the weight of each edge is either 1 or −1 and for each vertex i, the product of the edge weights of all edges having i as one endpoint is −1.

You are given a positive integer n There are nn−2⋅2n−1distinct†† edge-weighted trees with n vertices numbered from 11 to n such that each edge is either 1 or −1. Your task is to find the sum of d(1,n)‡ of all such trees that are good. Since the answer can be quite large, you only need to find it modulo 998244353998244353.

†† Two trees are considered to be distinct if either:

there exists two vertices such that there is an edge between them in one of the trees, and not in the other.
there exists two vertices such that there is an edge between them in both trees but the weight of the edge between them in one tree is different from the one in the other tree.

Note that by Cayley's formula, the number of trees on n labeled vertices is n^n−2. Since we have n−1 edges, there are 2n−1 possible assignment of weights(weight can either be 1 or −1). That is why total number of distinct edge-weighted tree is n^n−2⋅2n−1.

Input

The first and only line of input contains a single integer n (1≤n≤5⋅105).

Output

The only line of output should contain a single integer, the required answer, modulo 998244353.

Examples

input

output

948359297

input

output

86232114

题意：

给一棵n个点的树，树上每条边有权值1或-1，每个节点所有的边的乘积为-1，求所有情况的树上，从1到n路径权值的和

思路：

如果n为奇数，-1的个数为奇数，每条边贡献2个-1，不符题意

枚举所有对答案有贡献的边，一定在1到n的路径上，这条边把树分成两棵树，一边是1，一边是n，设大小为 i 和 n-i ，树中的点共有C（n-2，i-1）种选择，树的形状个数为 i ^(i-2) 和 (n-i)^(n-i-2)，每种形状边有 i*(n-i) 种选择，如果 i 为奇数，则边为-1，否则为1，枚举 i 统计答案

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<'='<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int INF=0x3f3f3f3f;#define int long long
const int N=5e5+5;
int mod=998244353;
int fact[N],inv[N];		//O(1)求组合数
ll qpow(ll a,ll b){ll ans=1;while(b>0){if(b&1)ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;
}
void Cinit(){fact[0]=1,inv[0]=1;for(int i=1;i<=N-1;i++){fact[i]=fact[i-1]*i%mod;inv[i]=inv[i-1]*qpow(i,mod-2)%mod;}
}
int C(int a,int b){if(a<0||b<0||a<b)return 0;return fact[a]*inv[a-b]%mod*inv[b]%mod;
}void solve(){int n;cin>>n;Cinit();int ans=0;for(int i=1;i<=n-1;i++){int tmp=pow(-1,i);tmp=tmp*i*(n-i)%mod;tmp=tmp*qpow(i,i-2)%mod*qpow(n-i,n-i-2)%mod*C(n-2,i-1)%mod;ans=(ans+tmp)%mod;}ans=(ans+mod)%mod;if(n&1)ans=0;cout<<ans<<endl;return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;//cin>>T;while(T--){solve();}return 0;
}