2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) D Contest Strategy

七月 30, 2021

组合数学

题目概述

你正在参加一场ACM比赛。已知自己每个题解决的用时。现在你随机开了$k$道题，然后找用时最短的做了，然后再随机开一道，再选用时最短的做了。现在考虑所有开题顺序$n!$中可能，求所有情况的罚时总和。

数据范围

$1 \leq k<n\leq 300$

分析与解

这个题求解真是构造和分析小数据起了很大的作用。“随机”并不可怕，只要把情况都考虑全了就没有问题。

首先说一些简单的性质。就是我们可以记$f[i][j]$表示第i个题是第j个做的（注意不是开是做！）。那么很显然可以给答案贡献$f[i][j] \cdot t[i]\cdot(n-j+1)$。所以问题转化为怎么求解$f[i][j]$.

我们不妨看几个例子。令$k=5$比如下面几个状态的4号题（用时也是4个单位时间）前两个第4个做的，第三组是第3个做的：

$\text{1 2 8 9 10} \; \underline{4} \;\text{3 5}\\ \text{1} \; \underline{4} \;\text{8 9 10 2 3 5}\\ \text{6 7 8 9 10 5} \; \underline{4} \; 3$

我们从中发现几件事：

为了方便，我们把题目按照解决用时从小到大排序。

首先，如果$i$号题是第$j$个做的，那么到这个题做的时候，已经开了$k-1+j$个题。而且当这个题做的时候，此时开了且没做的题目一定是用时比这个题长的。

令$r=min(k-i+j,n)$表示已经开了的题数目，$l$为已经开了的题目中用时比这个题短的。

因此$f[i][j]$一定包含乘积项$A_{n-i}^{r-1-l}$

那么回到上面举的例子，很有可能某个题先开了，但是过了几轮才做，这是因为一直存在比它用时小的题目。所以我们要在计数中枚举比它用时短的题目及其排列，所以$f[i][j]$包含乘积项$A_{i-1}^{l}$

由于题目要求开题都是有序的（$n!$种情况），因此我们枚举这道题是什么时候开的，以及比他用时短的题目都分别是什么时候开的，因此答案会有乘积项$r \cdot C_{r-1}^{l}$

最后我们再考虑这个题目解决后剩下题目的解决顺序，有乘积项$(n-r)!$

这样我们就得到

$f[i][j]=\sum_{l=0}^{j}r\cdot C_{r-1}^{l} \cdot A_{i-1}^{l}\cdot A_{n-i}^{r-1-l} \cdot(n-r)!$

但是我们立刻会发现问题，就是在枚举这个题开题和比他用时短的题目开题顺序时其实并不能这样直接用组合数算，因为这样有些情况导致$i$号题提前做了。但是我们发现这样的枚举，总是可以保证$i$号题是前$j$个被解决的题。因此我们修改$f[i][j]$的含义是第i个题是前j个做的，最后再容斥一下用$f[i][j]-f[i][j-1]$去贡献答案即可。

复杂度为$O(n^3)$

代码

#include <bits/stdc++.h>
using namespace std;
int mread() {
	int ret=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9') {
		if(c=='-')f=-1;
		c=getchar();
	}
	do {
		ret=ret*10+c-'0';
		c=getchar();
	} while('0'<=c && c<='9');
	return ret*f;
}
typedef long long LL;
LL combo[330][330];
LL t[330],ans=0;
int n,k;
const int MOD=1e9+7;
LL CC(int n,int m) {
	if(n<0 || n<m || m<0)return 0;
	return combo[n][m];
}
LL f[330][330];
LL fac[330];
int main() {
	int r;
	LL tmp,cnt;
	n=mread(),k=mread();
	for(int i=1; i<=n; i++)t[i]=mread();
	sort(t+1,t+n+1);
	for(int i=0; i<=n; i++)combo[i][0]=1;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			combo[i][j]=(combo[i-1][j]+combo[i-1][j-1])%MOD;
	fac[0]=1;
	for(int i=1; i<=n; i++)fac[i]=1ll*fac[i-1]*i%MOD;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			r=min(j+k-1,n);
			for(int l=0; l<j; l++) {
				f[i][j]=(f[i][j]+1ll*r*CC(i-1,l)%MOD*CC(r-1,l)%MOD*fac[l]%MOD*CC(n-i,r-1-l)%MOD
				         *fac[r-1-l]%MOD*fac[n-r]%MOD+MOD)%MOD;
			}

		}
	}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
		{
			cnt=f[i][j]-f[i][j-1]+MOD;
			ans=(ans+1ll*t[i]*(n-j+1)%MOD*cnt%MOD+MOD)%MOD;
		}
	printf("%lld\n",ans);
	return 0;
}

杂谈

注意题目用时可能一样，但实际上是不同的题目。这里确实是在$A_{i-1}^l$步有问题，但是可以通过容斥来弥补。

查看评论