#C241116B. 挂分

标签（Label）

• 数学
• 观察+分析

网址（Website）

题目详情 - 挂分 - Super

题解 - 挂分 - Super

题目（Problem）

样例

输入数据 1

3
1 2 3
2

输出数据 1

4

【样例 1 解释】

可能的挂分情况有 $\{0,0,0\}$，$\{1,0,0\}$，$\{0,0,1\}$，$\{1,0,1\}$ 。

注意 $\{1,0,2\}$ 不是合法的挂分情况，因为第三个人挂了 $2$ 分后，得分低于第二个人。

注意 $\{1,1,1\}$ 不是合法的挂分情况，因为第 $x=2$ 个人不能挂分。

注意 $\{2,2,2\}$ 不是合法的挂分情况，因为第一个人不能挂掉比自己原本更高的分。

输入数据 2

5
1 1 2 3 5
4

输出数据 2

12

【样例 3】

见选手目录下的 fate/fate3.in 和 fate/fate3.ans。

【样例 4】

见选手目录下的 fate/fate4.in 和 fate/fate4.ans。

题解（Solution）

44分

考虑 $\mathrm{dp}$ 。设 $f_{i,j}$ 表示当前位置为 $i$ ，当前值取 $j$ 的方案数，设 $A$ 表示值域，很明显左边和右边可以分开做，然后计算最后的答案。

先考虑左边的情况，手推可得， $f_{i,j}=\sum_{k=j}^{j+a_{i+1}-a_i}f_{i+1,k}$ ；对于右边的情况， $f_{i,j}=\sum_{k=j}^{a_{i-1}-a_i+j}f_{i-1,k}$ 。特别的，对于不会挂分的 $p$ 位置，有 $f_{p-1,j}=1\vert j\in[0,a[p]]$ 和 $f_{p+1,j}=1 | j\in[a[p],A]$ 。

最后的答案就是 $\sum_{j=0}^A f_{1,j}\times \sum_{j=0}^A f_{n,j}$ 。时间复杂度 $O(nA)$ 。

注意：实现可能与上面讲的不一样，但是上面讲的要更加简单一些。

52分

从上面的式子可以推得，对于每个转移，我们先考虑左边的情况，对于 $a_i$ 位置还剩 $j$ 分，我们能从 $a_{i+1}$ 转移必须满足他们的 $b_i\le b_{i+1}$ ，又因为 $b_i=a_i-j$ ，令上一个状态还剩 $k$ 分，则有 $a_i-j\le a_{i+1}-k \Rightarrow k\le a_{i+1}-a_i+j$ 又因为升序的限制，则 $k\in[j,j+a_{i+1}-a_i]$ ，由于最开始的时候所有有值的 $f_i$ 都是 $1$ ，我们发现向前推的时候每个点都会进行这样的转移，则有 $f_{i,j} = \sum_{k=j}^{j+a_{i+1}-a_i}f_{i+1,k} = f_{i+1,j}\times(a_{i+1}-a_i+1)$ ，那么左侧的答案其实就是 $(a_1+1)\times\Pi_{i=2}^{p-1} (a_{i+1}-a_i)$ ，结合上面的实现，一共可以拿 $52$ 分。

100分

和 $52$ 分的一种思路，我们通过打出大样例的每一个 $f_{i,j}$ ，惊奇的发现右边好像只有 $a_{p+1}-a_p$ 的部分不为 $0$ ，那么我们就只拿出这 $a_{p+1}-a_p$ 份，并且列成一个表格，惊奇的发现这个表格像是一个斜着的杨辉三角，那么就可以直接用组合数来做这道题了，经过观察得知， $f_{n,j}=\binom{(n-p)+j-1}{j}$ ，由于 $a_i\le 10^8$ ，我们完全可以通过这道题。

注意特判 $p=n$ 的情况。

出题者题解

### 算法分析

题目来源：原创。

对于 $n, a_i \leq 9$ 的部分分，可以考虑搜索出所有可能的情况，复杂度 $O(n^n)$。

不难发现，$x$ 左右两边是独立的，因为左边的人分数始终不超过 $a_x$，右边的人分数始终不低于 $a_x$，因此可以考虑将问题拆成 $x$ 左边和 $x$ 右边，然后用乘法原理计算答案。在 $x = \lfloor \frac{1 + n}{2} \rfloor$ 的情况，不难发现搜索的规模可以减半。

我们接下来单独考虑 $x$ 分别在左右侧的情况，也就是 $x = 1$ 和 $x = n$ 的部分分。

考虑 $x = 1$，也就是要求 $x$ 右侧的不降序列，再减去一个不增序列，仍然是一个不降序列，且要求最终序列第一个元素不小于 $a_x$。

不难发现，在这种情况下，如果最终序列第一个元素不小于 $a_x$ 的要求被满足，后面的元素依然还是不降的（后面更大的元素，减去了一个更小的数，显然还是不会比你小）。

令 $len = n - x$，$d = a_{x + 1} - a_x$，那么问题变成了数长度为 $len$，值域在 $[0, d]$ 的序列个数。

这个很经典，答案为 $\binom{d + len}{len}$。

考虑 $x = n$ 咋做。

也就是要求一个不降序列，减去一个不降序列还是不降序列。

这个限制就没有那么简单了。

但是还是可以考虑 $dp$ 并且使用前缀和优化做到 $O(nd)$。

设现在被减掉的序列是 $b$，那么 $b$ 序列合法的必要条件是：
$$
\forall i \in [1, x), a_i - b_i \geq a_{i-1} - b_{i-1}
$$
(不妨假设, $a_0 = b_0 = 0$)​

移项得到：

$$
\forall i \in [1, x), a_i - a_{i-1} \geq b_i - b_{i-1}
$$
不难发现这个条件也是充分的。

$a_i’ = a_i - a_{i-1}$，$b_i’ = b_i - b_{i-1}$，那么最终形式就是：

$$
\forall i \in [1, x), a_i’ \geq b_i’
$$
注意到 $b$ 和 $b’$ 一一对应，因此只需要算出 $b’$ 的方案数，就可以算出 $b$ 的方案数，而 $b’$ 的方案数显然是：

$$
\prod_{i=1}^{x-1} (a_i’ + 1)
$$
直接算即可。

最后只需要将前面部分和后面部分拼起来，就可以得到答案。

代码（Code）

44分

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 301234;
const int mod = 998244353;
bool ST;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void sub(int &x,int y){if((x-=y)<0)x+=mod;}

int n,p,a[N];
int f[5005][5005];

void Solve(){                       
	n=rd();For(i,1,n) a[i]=rd();p=rd();
	
	f[p][a[p]] = 1;
	Rof(i,p-1,1){
		int leijia = 0, tp = a[i+1];
		Rof(j,a[i+1],0){
			add(leijia, f[i+1][j]);
			while((i+1!=p) && a[i]-j > a[i+1]-tp) sub(leijia, f[i+1][tp]), tp--;
			f[i][j] = leijia;
		}
	}
	For(j,a[p],a[p+1]) f[p+1][j] = 1;
	For(i,p+2,n){
		int leijia = 0;
		Rof(j,a[i-1],0){
			add(leijia, f[i-1][a[i-1]-j]);
			f[i][a[i]-j] = leijia;
		}
	}int ans1=0, ans2=0;
	For(i,0,a[1]) add(ans1, f[1][i]);
	For(i,0,a[n]) add(ans2, f[n][i]);
	printf("%lld\n", ans1*ans2%mod);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("fate.in","r",stdin);
	freopen("fate.out","w",stdout);
	int Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

52分

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 301234;
const int mod = 998244353;
bool ST;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void sub(int &x,int y){if((x-=y)<0)x+=mod;}
inline void mul(int &x,int y){x=x*y%mod;}

int n,p,a[N];
int f[10005][10005];

void Solve(){                       
	n=rd();For(i,1,n) a[i]=rd();p=rd();
	
	f[p][a[p]] = 1;
	For(j,a[p],a[p+1]) f[p+1][j] = 1;
	For(i,p+2,n){
		int leijia = 0;
		Rof(j,a[i-1],0){
			add(leijia, f[i-1][a[i-1]-j]);
			f[i][a[i]-j] = leijia;
		}
	}
	
	int ans1=1, ans2=0;
	For(i,1,p-1) ans1 = ans1*(a[i]-a[i-1]+1)%mod;
	For(i,0,a[n]) add(ans2, f[n][i]);
	cerr<<ans1<<' '<<ans2<<'\n';
	printf("%lld\n", ans1*ans2%mod);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("fate.in","r",stdin);
	freopen("fate.out","w",stdout);
	int Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

100分

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 301234;
const int mod = 998244353;
bool ST;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void sub(int &x,int y){if((x-=y)<0)x+=mod;}
inline void mul(int &x,int y){x=x*y%mod;}
inline int ksm(int x,int k=mod-2){
	int res=1;while(k){
		if(k&1) mul(res,x);
		mul(x,x), k>>=1;
	}return res;
}int fac[N],inv[N];
inline int C(int n,int m){
	if(n==0 || m==0 || n==m) return 1;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int n,x,a[N];

void Solve(){
	fac[0] = 1;For(i,1,N-5) fac[i] = fac[i-1]*i%mod;
	inv[N-5] = ksm(fac[N-5], mod-2);
	Rof(i,N-6,1) inv[i] = inv[i+1]*(i+1)%mod;
	
	n=rd();For(i,1,n) a[i]=rd();x=rd();
	int z = 1, y = 1;
	if(x < n){
		y = C(n-x+a[x+1]-a[x], n-x);
	}
	if(x > 1){
		for(int i=1;i<x;i++){
			z = z*(a[i]-a[i-1]+1)%mod;
		}
	}printf("%lld\n",z*y%mod);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("fate.in","r",stdin);
	freopen("fate.out","w",stdout);
	int Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}