前行 - 2020校内常规测试Ⅰ

整理刷题记录时忽然看到第一条记录，已经是 2018/8 的记录了，将近两年，也仅有千多道题……

这场比赛的题都是教练不知道哪里拉来的，所以有可能碰到原题（那您真厉害）

---

# 题意

- A. 最大差值(diff.cpp)

给定一个长度为 $n$ 的字符串 $S$，取出一个子串 $T$，计算 “ $T$ 中出现得最多的字符的出现次数 减去 出现得最少（但是出现了）的字符的出现次数” 的最大值。

数据规模： $n\le 10^6$。

- B. 整除(div.cpp)

给定 $p$，求最小正整数 $n$ 使得 $n!\bmod p=0$。其中，$p$ 的计算方式为：

$$p=\sum_{i=1}^mP_i^{e_i}$$

$P_i$ 为第 $i$ 个质数。给定 $m$ 以及 $e_1,\dots,e_m$。

多组数据，数据组数在输入第一行给出，为 $T$。

数据规模：$T\le10^4,0\le P_ie_i\le10^{18},1\le m\le100$。

- C. 排列的和(sum.cpp)

设 $A,B$ 分别是 $1$ 到 $n$ 的排列。求有多少对不同的 $(A,B)$ 满足：

$$\sum_{i=1}^{n}\max\{A_i,B_i\}\ge m$$

Tab. 方案 $(A,B)$ 和 $(A’,B’)$ 不同当且仅当存在 $i$ 使得 $A_i\not=A’_i$ 或者 $B_i\not=B’_i$。

答案对 $998244353$ 取模。

数据规模：$1\le n\le50,1\le m\le10^9$。

---

# 解析

- A. 最大差值(diff.cpp)

我的脑回路可能和其他同学不一样……

唯一一样的可能就是第一步的贪心：我们所取的最优的区间一定是以下两种，

1. 区间的左右两端点都是区间中出现的最多的字符，这种情况下在这个区间内必须还有其他字符（不然就是 0 了）
2. 区间是由一整段相同字符再在左/右加上一个不同的字符。

所以区间的两端点至少会有一个是区间出现次数最多的。不妨假设是右端点，但是我们发现只有一种情况是计算不到的——上面所说的情况 2.，如果是必须在右边加一个不同的字符，那右端点就不是最大的字符了……

幸运的是，只有当前区间是原字符串 $S$ 的前缀，才会有这种只能在右边加一个不同的字符的情况。所以特殊处理一下就可以了。

然后我的做法就不太一样了。其他同学联想到最大子段和，于是滑窗解决（我好像不太懂滑窗）；我就写出了表达式：cnt[r][mx]-cnt[l-1][mx]-cnt[r][mn]+cnt[l-1][mn]，接下来我发现 $O(26n)$（26是字符集大小嘛）是可以接受的。

于是我选择枚举 r，于是 r 位置就是 mx；再枚举 mn，现在我们已经知道了表达式中 cnt[r][mx]-cnt[r][mn] 这一部分，然后还需要知道 cnt[l-1][mn]-cnt[l-1][mx] 的最大值，这个东西可以通过维护 pmx[mx][mn] 来实现的。

当然维护这个最大值很简单，只要每次计算完右端点为 r 的答案后，再把 l-1=r 的 mx 的贡献给更新一遍。

但是问题是这样没法保证区间内有两种以上字符（这种做法，如果一个区间只有一种字符，它会计算出“出现得最少的字符”的数量为0），这个就显然的 BUG。

另外要加两个补丁了：

1. 对于连续一段相同的字符一起处理；
2. 假如当前 r 位置的字符为 mx，那么用 las[mx]（mx 上一次出现的位置） 位置更新维护 pmx[mx][mn] 的。

还是挺麻烦的，可能需要看一下代码。

- B. 整除(div.cpp)

考场上根本没想过会卡常……

定义 $F(n,P_i)$ 表示 $n!$ 中有 $F(n,P_i)$ 个因数 $P_i$。根据“$P_i^a\times P_i^b=P_i^{a+b}$”，$F(n,P_i)$ 其实就是求 $1$ 到 $n$ 的每个数含有多少个因数 $P_i$。

然后有个勒让德定理，但是实际上你不知道这个定理也不重要，很好理解：

ll Calc(ll n,int P){ //F(n,P)
    ll ret=0;
    while(n>=P){
        ret+=n/P;
        n/=P;
    }
    return ret;
}

实际上自己手玩几遍就懂了。时间复杂度 $O(n\log_Pn)$，因为 $P$ 最小为 2，可以认为是 $O(n\log n)$。

更加显然的是如果 $n_0$ 满足要求，那么对于 $n_1>n_0$ 的 $n_1$ 也满足要求，于是就有了单调性。顺理成章地进行二分。二分左端点为 0（因为左端点取不到，实际上会计算到的最小值是 1），右端点是 $10^{17}$ 左右，当然为了保险取 $10^{18}$，然后非常难受地发现现在复杂度是 $O(n\log10^{18}\log n)$，在 $10^8$ 到 $10^9$ 之间。

就很容易卡常，所以计算的时候能剪枝就剪枝。

- C. 排列的和

这场考试里最重要的一道题吧？

发现 $n$ 很小很开心的样子 :P

我们发现因为 $A,B$ 都是排列，所以其实我们可以只求出两个排列中的元素对应关系，然后全排一下就可以得到全部答案，而且还不会重复。

如果 $A_i$ 和 $B_j$ 对应，那么它们的贡献为 $\max\{A_i,B_j\}$。为了保证贡献的唯一性，我们人为规定，当 $A_i=B_j$ 时取 $A_i$。于是 $A_i$ 想有贡献，就需要找一个小于等于它的 $B_j$ 匹配，如果 $B_j$ 想要有贡献，就需要找一个小于它的 $A_i$ 匹配。

于是可以 DP：f[i][j][k] 表示现在已经决定了 $A,B$ 中的 $1$ 到 $i$，其中 $A,B$ 分别有 $j$ 个数暂时没有匹配上（因为只考虑与比自己小/小于等于的数配对，所以可以看到当前 $A,B$ 未匹配的数量是一样的），此时的有贡献的数的和为 $k$。考虑 4 种转移：

Tab. 下面的符号定义有一些更改：$A_i$ 表示 $A$ 中的元素 $i$（不是第 $i$ 个元素），$B_i$ 同理。

1. $A_i,B_i$ 都不贡献，也就是说不与小于它的数匹配，于是未匹配的数量+1，k不变；即 f[i-1][j-1][k] -> f[i][j][k]
2. $A_i$ 贡献，但是 $B_i$ 不贡献，那么 $A_i$ 与 $B$ 中 $1$ 到 $i$ 的尚未匹配的数配对，不难得到此时 $B$ 中未匹配的数有 $j$ 个，$A_i$ 与任意一个匹配都有贡献，因此：f[i-1][j][k-i]*j -> f[i][j][k]
3. $B$ 中的 $i$ 贡献，那么 $B_i$ 就要与 $A$ 中的 $1$ 到 $i-1$（之前 $\max\{A_i,B_j\}$ 的规定）中未配对的匹配，此时 $A$ 中未匹配的数有 $j-1$ 个，因此：f[i-1][j][k-i]*(j-1) -> f[i][j][k]
4. $A_i,B_i$ 都贡献，那么 $A_i$ 肯定不能匹配 $B_i$，不然只会有一个贡献，于是 $A_i$ 要匹配 $B_{1\to i-1}$，$B_i$ 要匹配 $A_{1\to i-1}$，那么：f[i-1][j+1][k-2*i]*(j-1)*(j-1) -> f[i][j][k]

然后求 f[n][0][m~n^2] 的和就行了。

---

# （喜闻乐见的）源代码

- A. diff.cpp

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6,SC=26;
char str[N+5];
int n,ans;
int cnt[N+3][30],pmx[30][30],las[30];

int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	scanf("%d%s",&n,str+1);
	for(int i=1;i<=n;i++){
		for(int j=0;j<SC;j++)
			cnt[i][j]=cnt[i-1][j];
		cnt[i][str[i]-'a']++;
	}
	for(int i=0;i<SC;i++)
		for(int j=0;j<SC;j++)
			pmx[i][j]=-1e8;
	for(int r=1;r<=n;r++){
		int R=r,mx=str[r]-'a',mn;
		while(str[R+1]==str[r]) R++;
		if(r==1){
			if(R!=n)
				ans=max(ans,R-1);
		}
		else
			for(mn=0;mn<SC;mn++)
				ans=max(ans,cnt[R][mx]-cnt[R][mn]+pmx[mx][mn]);
		for(int i=r-1;i<R;i++)
			for(mn=0;mn<SC;mn++)
				pmx[mn][mx]=max(pmx[mn][mx],cnt[i][mx]-cnt[i][mn]);
		if(las[mx]){
			for(mn=0;mn<26;mn++)
				pmx[mn][mx]=max(pmx[mn][mx],cnt[las[mx]][mx]-cnt[las[mx]][mn]);
		}
		las[mx]=R;
		r=R;
	}
	printf("%d\n",ans);
	return 0;
}

- B. div.cpp

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int M=100,VAL=1000;

int cas,m;
ll po[M+5];
int P[VAL],np;
bool vis[VAL+3];

void Init(){
	for(int i=2;i<=VAL;i++){
		if(!vis[i]) P[++np]=i;
		for(int j=1;j<=np && P[j]*i<=VAL;j++){
			vis[P[j]*i]=true;
			if(i%P[j]==0) break;
		}
	}
}
bool Calc(ll n,int p,ll ext){
	ll cur=0;
	while(n){
		cur+=n/p;
		if(cur>=ext) return true;
		n/=p;
	}
	return false;
}
int main(){
//	freopen("input.txt","r",stdin);
	freopen("div.in","r",stdin);
	freopen("div.out","w",stdout);
	Init();
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&m);
		for(int i=1;i<=m;i++) scanf("%lld",&po[i]);
		ll lef=0,rig=(ll)1e18;
		while(lef+1<rig){
			ll mid=(lef+rig)>>1;
			bool pas=true;
			for(int j=1;j<=m && pas;j++)
				pas=Calc(mid,P[j],po[j]);
			if(pas) rig=mid;
			else lef=mid;
		}
		printf("%lld\n",rig);
	}
	return 0;
}

- C. sum.cpp

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MOD=998244353,N=50;

int n,m;
int f[N+3][N+3][N*N+3];

int main(){
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(m>n*n){printf("0\n");return 0;}
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i;j++)
			for(int k=0;k<=n*n;k++){
				if(j) f[i][j][k]+=f[i-1][j-1][k];
				if(k>=i) f[i][j][k]+=f[i-1][j][k-i]*(j+1ll)%MOD;
				if(f[i][j][k]>=MOD) f[i][j][k]-=MOD;
				if(k>=i) f[i][j][k]+=1ll*f[i-1][j][k-i]*j%MOD;
				if(f[i][j][k]>=MOD) f[i][j][k]-=MOD;
				if(k>=2*i) f[i][j][k]+=1ll*f[i-1][j+1][k-2*i]*(j+1)%MOD*(j+1)%MOD;
				if(f[i][j][k]>=MOD) f[i][j][k]-=MOD;
			}
	int ans=0;
	for(int k=m;k<=n*n;k++){
		ans+=f[n][0][k];
		if(ans>=MOD) ans-=MOD;
	}
	for(int i=1;i<=n;i++)
		ans=1ll*ans*i%MOD;
	printf("%d\n",ans);
	return 0;
}

---

THE END

Thanks for reading!

“生命情节究竟要如何更改，才不至于再让人觉得倦怠？”
——《世末积雨云》By COP