2020牛客暑期多校训练营（第六场）

B. Binary Vector $\looparrowright$

题目描述

Roundgod is obsessive about linear algebra. Let $\mathrm A=\{0,1\}$, everyday she will generate a binary vector randomly in $\mathrm A^n$. Now she wonders the probability of generating $n$ linearly independent vectors in the next $n$ days modulo $10^9+7$. Formally, it can be proved that the answer has the form of $\frac{P}{Q}$, where $P$ and $Q$ are coprime and $Q$ is not a multiple of $10^9+7$. The answer modulo $10^9+7$ thus means $P \cdot Q^{-1}\pmod{10^9+7}$, where $Q^{-1}$ is the multiplicative inverse of $10^9+7$.
Wcy thinks the problem too easy. Let the answer of $n$ be $f_n$, she wants to know $f_1\oplus f_2\oplus ...\oplus f_n$, where $\oplus$ denotes bitwise exclusive or operation.
Note that when adding up two vectors, the components are modulo $2$.

输入描述

The input contains multiple test cases. The first line of input contains one integer $T$ $(1\leqslant T\leqslant 1000 )$, denoting the number of test cases.
In the following $T$ lines, each line contains an integer $n$ $(1\leqslant n\leqslant 2\times 10^7 )$ describing one test case.

输出描述

For each test case, output one integer indicating the answer.

示例1

输入

3
1
2
3

输出

500000004
194473671
861464136

说明

$f(1)=\frac{1}{2}\\ f(2)=\frac{3}{8}\\ f(3)=\frac{21}{64}$

分析

首先说明，向量各个维度的坐标都是在模 $2$ 意义下的，基于此可以有如下性质。对于两个向量 $\vec a$ 和 $\vec b$，$\vec a+\vec b=\vec a-\vec b=\vec b-\vec a$，这三者可视为同一向量。对于一个向量 $\vec x$，$\forall\ k\in\mathbb N$，若 $k$ 为偶数，那么 $k\vec x=\vec 0$；若 $k$ 为奇数，那么 $k\vec x=\vec x$。基于以上，两个向量 $\vec a$ 和 $\vec b$ 的线性组合只有 $\vec a,\vec b,\vec a+b,\vec 0$ 这四个向量。
$f_n$ 表示随机生成 $n$ 个线性无关的 $n$ 维向量的概率。由于要使 $n$ 个 $n$ 维向量组成的向量组线性无关，因此考虑添加第 $i$ 个 $n$ 维向量 $\vec x$ 时，$\vec x$ 必须不属于前 $i-1$ 个线性无关的向量构成的向量空间。接下来尝试枚举 $i$ 来寻找规律。
当 $i=2$，已有的线性无关向量组为 $\vec a$；同 $\vec a$ 组成线性相关向量组的向量有 $\vec 0,\vec a$。当 $i=3$，已有的线性无关向量组为 $\vec a,\vec b$，那么同 $\vec a,\vec b$ 构成线性相关向量组的向量有 $\vec 0,\vec a,\vec b,\vec a+\vec b$。当 $i=4$，已有的线性无关向量组为 $\vec a,\vec b,\vec c$，那么同 $\vec a,\vec b,\vec c$ 构成线性相关向量组的向量有 $\vec 0,\vec a,\vec b,\vec c,\vec a+\vec b,\vec a+\vec c,\vec b+\vec c,\vec a+\vec b+\vec c$。基于以上，假设已经存在 $i-1$ 个线性无关的向量 $\vec{\alpha_1},\vec{\alpha_2},\cdots,\vec{\alpha_{i-1}}$，如果再添加一个向量 $\vec x$，使得 $\vec{\alpha_1},\vec{\alpha_2},\cdots,\vec{\alpha_{i-1}},\vec x$ 线性相关，那么 $\vec x$ 的取值有 $\sum\limits_{j=0}^{i-1}\binom{i-1}{j}=2^{i-1}$ 种；该式意味着每次在 $i-1$ 个向量中取 $j$ 个向量 $\vec{\alpha_{i_1}},\vec{\alpha_{i_2}},\cdots,\vec{\alpha_{i_j}}$，令 $\vec x=\vec{\alpha_{i_1}}+\vec{\alpha_{i_2}}+\cdots+\vec{\alpha_{i_j}}$。
第 $i$ 个向量是 $n$ 维向量，必然有 $2^n$ 种可能；但是由于已经存在 $i-1$ 个线性无关的向量，因此其中 $2^{i-1}$ 种取值必然会与前 $i-1$ 个向量组成线性相关的向量组，只有 $2^n-2^{i-1}$ 种取值是合法的。因此，第 $i$ 个向量与前 $i-1$ 个线性无关的向量组成线性无关组的概率为 $\frac{2^n-2^{i-1}}{2^n}$。故当 $n\geqslant 2$ 时，$n$ 个 $n$ 维向量组成线性无关组的概率 $f_n=\frac{1}{2}\prod\limits_{i=2}^n\frac{2^n-2^{i-1}}{2^n}=\prod\limits_{i=1}^n\frac{2^n-2^{i-1}}{2^n}$；显然，当 $n=1$ 时符合上式，故 $f_n=\prod\limits_{i=1}^n\frac{2^n-2^{i-1}}{2^n}$。
可见，$f_n=\frac{(2^n-1)(2^n-2)\cdots(2^n-2^{n-1})}{2^{n^2}}$，而 $f_{n-1}=\frac{(2^{n-1}-1)(2^{n-1}-2)\cdots(2^{n-1}-2^{n-2})}{2^{(n-1)^2}}$。因此有 $2^{n-1}f_{n-1}=\frac{(2^n-2)\cdots(2^n-2^{n-1})}{2^{(n-1)^2}}$，故 $\frac{f_n}{2^{n-1}f_{n-1}}=\frac{2^n-1}{2^{2n-1}}$。最终得到 $f_{n}=\left(1-\frac{1}{2^n}\right)f_{n-1}$，已知 $f_1=\frac{1}{2}$。预处理 $2$ 的幂的逆元后，即可 $O(n)$ 得到 $f_n$ 的值，再处理 $f_n$ 的异或前缀和，每次查询 $O(1)$ 输出答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem B
Date: 8/26/2020
Description: Liner Algebra, Probability Theory
*******************************************************************/
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int N=20000000;
int _;
ll f[N+2];
ll inv2[N+2];
ll ans[N+2];
int n;
void init();
ll qpow_mod(ll,ll);
int main(){
	init();
	for(cin>>_;_;_--){
		scanf("%d",&n);
		printf("%lld\n",ans[n]);
	}
	return 0;
}
void init(){
	int i;
	inv2[1]=qpow_mod(2,mod-2);
	//inv(2^n)=inv(2)^n
	for(i=2;i<=N;i++){
		inv2[i]=inv2[i-1]*inv2[1]%mod;
	}
	f[1]=inv2[1];
	for(i=2;i<=N;i++){
		f[i]=(1-inv2[i]+mod)*f[i-1]%mod;
	}
	ans[1]=f[1];
	for(i=2;i<=N;i++){
		ans[i]=f[i]^ans[i-1];
	}
}
ll qpow_mod(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1){
			res=res*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

C. Combination of Physics and Math $\looparrowright$

题目描述

Roundgod has an $n \times m$ matrix $A = (a_{ij})$. One day while she’s doing her physics homework, she wonders is it possible to define the physical quantity for matrices.
As we all know, the pressure $p$ satisfies a formula $p=\frac{F}{S}$, where $F$ is the compressive force and $S$ is the base area.
To describe it in maths, Roundgod puts forward that the compressive force of a matrix equals the sum of all its entries, while the base area of a matrix equals the sum of the entries in its last row. Then she can calculate the pressure for a matrix with the same formula.
Your goal is to find the submatrix of AA with maximum pressure.
A submatrix is obtained by taking nonempty subsets of its rows and columns. Formally, given a nonempty subsequence $S$ of $\{1,2, \ldots, n\}$ and a nonempty subsequence $T$ of $\{1, 2, \ldots, m\}$, then $\begin{pmatrix} a_{S_1, T_1} & a_{S_1, T_2} & \cdots & a_{S_1, T_{|T|}} \\ a_{S_2, T_1} & a_{S_2, T_2} & \cdots & a_{S_2, T_{|T|}} \\\vdots & \vdots & \ddots & \vdots \\ a_{S_{|S|}, T_1} & a_{S_{|S|}, T_2}&\cdots & a_{S_{|S|}, T_{|T|}} \end{pmatrix}$ is a submatrix of $A$.

输入描述

There are multiple test cases. The first line of input contains an integer $T\ (T\leqslant 100)$, indicating the number of test cases. For each test case:
The first line contains two integers $n, m\ (1\leqslant n,m\leqslant 200)$, the number of rows and columns of the matrix, respectively.
Each of the next $n$ lines contains $m$ integers, specifying the matrix $(1\leqslant a_{ij}\leqslant 5\times 10^4)$.

输出描述

For each test case, print the maximum pressure within an absolute or relative error of no more than $10^{-8}$ in one line.

示例1

输入

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

输出

4.50000000

说明

$\begin{pmatrix}1 & 5\\6 & 9 \\2 & 4\end{pmatrix}$ is one of submatrices of $A$ with maximum pressure $\frac{1+5+6+9+2+4}{2+4}=\frac{27}{6}=4.5$.

分析

$\forall\ a,b,c,d\in \mathrm N^\ast$，若 $\frac{a}{b}\leqslant \frac{c}{d}$，那么 $\frac{a}{b}\leqslant\frac{a+b}{c+d}\leqslant\frac{c}{d}$。因此，若选择的子矩阵有多列，将其拆成两个行数相同的更小的子矩阵，一定有一个小子矩阵的压强大于等于原子矩阵的压强。所以，最优的子矩阵应当只有一列。
若 $a_{ij}$ 为一个子矩阵的底面积，贪心地取 $a_{1j},a_{2j},\cdots,a_{ij}$ 为子矩阵（$a_{ij}$ 正上方的所有元素），其压强是所有以 $a_{ij}$ 为底面积的子矩阵中压强最大的。枚举 $a_{ij}$，即可在 $O(nm)$ 内求得答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem C
Date: 8/26/2020
Description: Inequality
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=202;
int _;
int n,m;
int a[N][N];
double sum[N][N];
int main(){
	for(cin>>_;_;_--){
		scanf("%d%d",&n,&m);
		int i,j;
		for(i=1;i<=n;i++){
			for(j=1;j<=m;j++){
				scanf("%d",&a[i][j]);
			}
		}
		//预处理每一列的前缀和
		for(j=1;j<=m;j++){
			for(i=1;i<=n;i++){
				sum[j][i]=a[i][j]+sum[j][i-1];
			}
		}
		double ans=0;
		for(i=1;i<=n;i++){
			for(j=1;j<=m;j++){
				ans=max(ans,sum[j][i]/a[i][j]);
			}
		}
		printf("%.8lf\n",ans);
	}
	return 0;
}

E. Easy Construction $\looparrowright$

题目描述

Roundgod is given $n, k$, construct a permutation $P$ of $1\sim n$ satisfying that for all integers $i$ in $[1, n]$, there exists a contiguous subarray in $P$ of length $i$ whose sum is $k$ modulo $n$. If there are multiple solutions, print any of them. If there is no solution, print “-1” in one line.

输入描述

The first line contains two integers $n$, $k$ $(1\leqslant n \leqslant 5000, 0\leqslant k < n)$.

输出描述

Print $n$ integers, the answer permutation in one line if such permutation exists, or print “-1” in one line if no solution exists.

示例1

输入

2 1

输出

1 2

说明

The sum of subintervals $[1],[1,2]$ both satisfy $\equiv 1 \pmod{2}$, and their lengths are $1,2$ respectively.

示例2

输入

3 1

输出

-1

分析

$\forall\ i\in[1,n]$，$P$ 存在子列满足，子列各个元素的和与 $k$ 模 $n$ 同余；当 $i=n$ 时，子列的和为 $\sum\limits_{i=1}^n P_i=\sum\limits_{i=1}^n i=\frac{n(n+1)}{2}$，故 $\frac{n(n+1)}{2}\equiv k\pmod n$。
当 $n$ 为奇数，若 $k=0$，则有解；令 $P=[n,1,n-1,2,n-2,\cdots]$ 即可。
当 $n$ 为偶数，若 $k=\frac{n}{2}$，则有解；令 $P=\left[n,\frac{n}{2},1,n-1,2,n-2,\cdots\right]$ 即可。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem E
Date: 8/24/2020
Description: Construction
*******************************************************************/
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	if(n&1){
		if(!k){
			cout<<n;
			for(register int i=1;i<=n/2;i++){
				printf(" %d %d",i,n-i);
			}
			putchar('\n');
		}else{
			puts("-1");
		}
	}else{
		if(k==n/2){
			cout<<n<<' '<<n/2;
			for(register int i=1;i<n/2;i++){
				printf(" %d %d",i,n-i);
			}
			putchar('\n');
		}else{
			puts("-1");
		}
	}
	return 0;
}

H. Harmony Pairs $\looparrowright$

题目描述

Roundgod is obsessive about numbers. Let $S(x)$ be the sum of the digits of $x$ in decimal notation, $(A,B)$ is a harmony pair if and only if $S(A)>S(B)$. Roundgod is given $N$, and she wants to count the number of harmony pairs $(A,B)$ modulo $10^9+7$ satisfying $0\leqslant A\leqslant B\leqslant N$.

输入描述

The only line of input contains one integer $N\ (1\leqslant N\leqslant 10^{100} )$.

输出描述

Output one integer indicating the answer.

示例1

输入

100

输出

967

比较套路的数位 $\mathrm {DP}$ 问题。
$N$ 的数位长度为 $len$，同时构造 $A,B$ 的第 $1,2,\cdots,len$ 位（数位自左向右，左边的数位小），采用记忆化搜索的形式。$limit_1$ 表示对 $B$ 的限制，限制 $B\leqslant N$；$limit_2$ 表示对 $A$ 的限制，限制 $A\leqslant B$。定义 $f(p,q,r,s)$ 表示 $A,B$ 有 $p$ 位，$S(A)-S(B)=q$，$limit_1=r$ 且 $limit_2=s$ 时，构造 $A,B$ 的方案数。由于 $S(A)-S(B)$ 有可能为负数，所以需要加上 $1000$ 的偏移量。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem H
Date: 8/27/2020
Description: Digit Dynamic Programming
*******************************************************************/
#include<iostream>
#include<cstring>
using namespace std;
const int N=102;
const int mod=1000000007;
int f[N][N*22][2][2];
int number[N];
int len;
char str[N];
int dfs(int pos,int difference,bool limit1,bool limit2){
	if(pos==len+1){
		//减去偏移量差值大于0表示可行
		return difference>1000;
	}
	if(~f[pos][difference][limit1][limit2]){
		return f[pos][difference][limit1][limit2];
	}
	int res1=limit1?number[pos]:9;
	int ans=0;
	for(register int i=0;i<=res1;i++){
		//枚举B的数位
		int res2=limit2?i:9;
		for(register int j=0;j<=res2;j++){
			//枚举A的数位
			ans+=dfs(pos-1,difference+j-i,i==res1&&limit1,i==j&&limit2);
			ans%=mod;
		}
	}
	f[pos][difference][limit1][limit2]=ans;
	return f[pos][difference][limit1][limit2];
}
int main(){
	cin>>(str+1);
	len=strlen(str+1);
	//12345
	for(register int i=1;i<=len;i++){
		//按照习惯排列
		number[i]=str[i]-'0';
	}
	memset(f,-1,sizeof(f));
	cout<<dfs(1,1000,1,1)<<endl;
	return 0;
}

K. K-Bag $\looparrowright$

题目描述

A sequence is called $k$-bag, if and only if it is put in order by some (maybe one) permutations of $1$ to $k$. For example, $[1,2,3,2,1,3,3,2,1]$ is a valid $3$-bag sequence.
Roundgod is not satisfied with kk-bag, so she put forward part-kk-bag, which is a contiguous subsequence of $k$-bag.
Wcy wants to know if the sequence of length $n$ is a part-$k$-bag sequence.

输入描述

The first line contains one integer $T\ (1\leqslant T\leqslant 20)$, denoting the number of test cases. Then TT test cases follow.
The first line of each test case contains two integers $n,k\ (1\leqslant n \leqslant 5 \times 10^5,1\leqslant k \leqslant 10^9)$.
The second line of each test case contains $n$ integers indicate the sequence.
It is guaranteed that $\sum n \leqslant 2\times 10^6$, the values of the sequence are between $1$ and $10^9$.

输出描述

One line of each test case, if the sequence is a part-$k$-bag sequence, print “YES”, otherwise print “NO”.

示例1

输入

1
8 3
2 3 2 1 3 3 2 1

输出

YES

分析

设给出的序列为 $a$。
首先，若 $\exists\ a_i\not\in[1,k]$，那么给出的 $a$ 必然不是 part-$k$-bag，可以直接输出 “NO”。接下来的讨论皆基于 $\forall a_i$，$a_i\in[1,k]$ 的情况。
若 $a$ 各个元素互不相同，那么 $a$ 可能恰好是 $1\sim k$ 的全排列，也可能是一个 $1\sim k$ 的全排列的一个子序列；根据 $k$-bag 的定义，此时的 $a$ 必然是个 part-$k$-bag。
若 $\exists\ a_i=a_j$，那么情况就类似样例 $[2,3,2,1,3,3,2,1]$。$a$ 的头和尾是 $1\sim k$ 的全排列的一部分，而中部是多个 $1\sim k$ 的全排列。显然，对于 $a_i$ 和 $a_j$，若 $a_i=a_j$，那么两者必然不会在同一个排列中。令 $d$ 为满足 $i<d$ 且 $a_i=a_d$ 的最小整数。那么 $a$ 头部的结尾位置最大为 $d-1$，否则 $a$ 的头部包含两个相同的数，不满足排列的定义。从 $1$ 到 $d-1$ 枚举 $a$ 的头部结尾，每次检验接下来的序列是否能构成多个 $1\sim k$ 的全排列即可，当然，检验时，$a$ 的尾部是很好识别的。为了做到 $O(n)$ 的时间复杂度，可以采用双指针。定义两个指针 $l,r$，$l$ 表示当前 $a$ 头部结尾的位置。最初 $l=1$，$r$ 从 $2$ 开始，不停地向后找 $k$ 的全排列，因此可$r$ 理解为当前尚未检验过的序列的开头。维护 $cnt_x$ 表示 $x$ 在当前考察序列（当前考察序列指 $a_{l+1}\sim a_{r-1}$ 这部分序列）内出现的次数；$a$ 的中部会有多个全排列，用 $ID$ 表示当前正在检验的全排列的编号，从 $1$ 开始记录。假设已经检验完 $ID-1$ 个全排列，当前正在检验第 $ID$ 个全排列，由于 $r$ 表示还未检验到的序列开头，那么当且仅当 $cnt_{a_r}=ID-1$ 时，前面有 $ID-1$ 个全排列；否则，说明当前的 $l$ 作为头部的结尾不能使 $a$ 成为 part-$k$-bag，应当继续枚举 $l$。若 $l$ 一直枚举到 $d$ 还未找到 $a$ 成为 part-$k$-bag 的方案，那么 $a$ 就不是 part-$k$-bag。
注意要用 \text{unordered_set} 和 \text{unordered_map}，$\text{set}$ 和 $\text{map}$ 则容易超时。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem K
Date: 8/27/2020
Description: Double Pointer
*******************************************************************/
#include<unordered_map>
#include<cstdio>
#include<iostream>
#include<unordered_set>
using namespace std;
const int N=500004;
int _;
int a[N];
int n,k;
int main(){
	for(cin>>_;_;_--){
		scanf("%d%d",&n,&k);
		int i;
		bool flag=0;
		for(i=1;i<=n;i++){
			scanf("%d",a+i);
		}
		for(i=1;i<=n;i++){
			//超出范围
			if(a[i]<1||a[i]>k){
				flag=1;
				break;
			}
		}
		if(flag){
			puts("NO");
		}else{
			unordered_set<int>ex;
			int d;
			for(i=1;i<=n;i++){
				if(ex.count(a[i])){
					//保证d是满足条件的最小整数
					d=i;
					break;
				}else{
					ex.insert(a[i]);
				}
			}
			if(ex.size()==n){
				//互不相同的n个数
				puts("YES");
			}else{
				bool is=1;
				int l=1,r=2;
				int ID=1;//当前要找的全排列编号
				int num=0;//一个全排列中已经遍历的数字个数
				unordered_map<int,int>cnt;
				while(r<=n){
					if(l==d){
						is=0;
						break;
					}
					bool find_permutation=1;
					while(r<=n){
						//若r能一直检验到n
						//那么这个l就是合法的
						if(cnt[a[r]]==ID-1){
							//a[r]可以在第ID个排列内
							cnt[a[r]]++;
							r++;
							num++;
							if(num==k){
							//找到一个全排列
							//继续找下一个
								num=0;
								ID++;
							}
						}else{
							//减去贡献
							num--;
							cnt[a[l+1]]--;
							l++;
							break;
						}
					}
				}
				puts(is?"YES":"NO");
			}
		}
	}
	return 0;
}