2022-7-7 personal qualifying 4 competition experience

 

  Algorithm is summarized ：

A： String bucket + violence

B： Combinatorial inverse

C： Stack simulation or dfs

D: Exclusive or + The meter

EFG: Water problem

J: structure

K: Minimum spanning tree

L： simulation

B: PERICA

subject ：

 Perica The piano is made of N Keys , Each key has a value ai. stay Perica When playing the piano , He will press just at the same time K Two different keys . This piano is a little strange , Because press at the same time K After keys , It can only play the key with the largest number .Perica Will play K Each combination of keys , He wants to know the sum of the maximum values in all combinations . The first line of the input contains two integers N, K (1<N<10,1<K<50). The second line contains a length of N Sequence a1,a2,,an (0<ai <10°). Output output and , Yes 10°+7 modulus .

Sample Input

5 3 2 4 2 3 4 5 1 1 0 1 1 1 5 2 3 3 4 0 0

Sample Output

39 4 31

Ideas ： Inverse element processing combination number

  Inverse element :a/b%p=(a*(b^(p-2))%p)%p

New template ：

 The combinatorial writing method of finding the remainder of large numbers 
int fastpower(int b,int p){
    int r=1;
    while (p>0){
        if (p%2==1){
            r=(r*b)%mod;
        }
        p=p/2;
        b=(b*b)%mod;
    }
    return r;
}
int c(int m,int n){
	if(m==0) return 1;
	if(m>n-m) m=n-m;
	int up=1,down=1;
	for(int i=1;i<=m;i++){
		up=(up*(n-i+1))%mod;
		down=(down*i)%mod;
	}
	return up*fastpower(down,mod-2)%mod;
}

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
int fastpower(int b,int p){
    int r=1;
    while (p>0){
        if (p%2==1){
            r=(r*b)%mod;
        }
        p=p/2;
        b=(b*b)%mod;
    }
    return r;
}
int c(int m,int n){
	if(m==0) return 1;
	if(m>n-m) m=n-m;
	int up=1,down=1;
	for(int i=1;i<=m;i++){
		up=(up*(n-i+1))%mod;
		down=(down*i)%mod;
	}
	return up*fastpower(down,mod-2)%mod;
}
int a[N];
bool cmp(int a,int b){
	return a>b;
} 
void work(){
	int n,k;cin>>n>>k;
	rep(i,1,n){
		cin>>a[i];
	} 
	sort(a+1,a+n+1,cmp);
	int sum=0;
	rep(i,1,n-k+1){
		sum+=a[i]*c(k-1,n-i);
		sum=sum%mod;
	}
	cout<<sum<<endl;
}
signed main(){
	CIO;
	work();
	return 0;
}

 D:OZLJEDA

Because of the crazy use of rackets to kill flies ,Marin Suffered serious physical injury called lateral epicondylitis of humerus in the medical community (?). His grandmother built , Discuss daubing rakija, The doctor also prescribed powerful painkillers , but Marin Ignore every suggestion , And decided to find the answer in the sequence of integers . He found a sequence of integers that had never been found before , And call it xorbonacci Sequence . The second in the sequence n Two elements with cn Express . The sequence is recursively defined in the following way :T1 = a C2 = a2Tk= akTn = n-1 Cn-2 n-k, n > k Because one has only Marin Know the reason , He decided that as long as you answer him Q A question , All his sadness will disappear . Each question will be given l and r. The answer to the query is expressed in the following formula τι Θ τl+1 r-1 ar help Marin Answer these questions . Be careful : operation 0 That is, bitwise XOR .

The first line of input contains an integer K (1<K<105). The second line contains K It's an integer , Express xorbonacci The front of the sequence K Elements . All numerical values are less than 1018 The third line contains an integer Q(1<Q<10°). then Q That's ok , The first i Line contains two integers l and r;, Express Marin Of the i Time to ask .(1<li<ri< 1018)

Output output one line of answer for each query .

Sample Input

4 1 3 5 7 3 2 2 2 5 1 5 5 3 3 4 3 2 4 1 2 1 3 5 6 7 9

Sample Output

3 1 0 0 4 7 4

Exclusive or ：x^x=0, Deal with prefix XOR .

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=2e6+5;
int a[N],p[N];
void work(){
	int k;cin>>k;
	int sum=0;
	rep(i,1,k){
		cin>>a[i];
		p[i]=p[i-1]^a[i];
	}
	a[k+1]=p[k];
	int q;cin>>q;
	int l,r;
	rep(i,1,q){
		cin>>l>>r;
		l=(l-1)%(k+1)+1;
		r=(r-1)%(k+1)+1;
		cout<<(p[r]^p[l-1])<<endl;
	}
}
signed main(){
	CIO;
	work();
	return 0;
}

H I read the question wrong in the exam ..