Pass to Next

题解

做过一遍的题再做一遍有不会了。

首先，我们发现，如果每个人都至少传了一个球，那么我们得到的最终的序列就会与去掉它们都串的球的最小值后的序列相同。
所以我们的答案可以用所有方案 − - −至少传一个球的方案得出，显然，总共有 ∏ ( a i + 1 ) − ∏ a i \prod(a_{i}+1)-\prod a_{i} ∏(ai​+1)−∏ai​种方案，但我们要求的答案是 ∑ ∏ x i \sum \prod x_{i} ∑∏xi​，这东西要怎么求呢？
考虑将这个乘积的式子用组合意义的方法转换一下， ∏ x i \prod x_{i} ∏xi​显然就是就是让每个人从自己的球中选出一个的方案数，所以我们需要求出所有传球方案的选球方案数。

上面的问题显然可以考虑用 d p dp dp求出，我们定义 d p i , 0 / 1 dp_{i,0/1} dpi,0/1​，考虑第 i i i个人，第 i i i个人在前一个人/他自己的球中选择球的方案数。
显然我们的转移应该是有两个部分内的，一个是他往后传球的部分，他选自己的球的部分。
如果他要在前面一个人的球中选球，那就应该在从 d p i − 1 − > d p i dp_{i-1}->dp_{i} dpi−1​−>dpi​时处理好他的方案。
如果他要在自己的球中选球，那就应该在从 d p i − > d p i + 1 dp_{i}->dp_{i+1} dpi​−>dpi+1​时处理好他的方案。
因为这两中选球的不同涉及到他或者他前面的人的传球方案。
转移应该还是比较好想的，主要就是枚举一下 d p i dp_{i} dpi​与 d p i + 1 dp_{i+1} dpi+1​的 0 / 1 0/1 0/1状态，总共四种转移。
下面以没有现在的方案为例，

• d p i , 0 − > d p i + 1 , 0 dp_{i,0}->dp_{i+1,0} dpi,0​−>dpi+1,0​，显然我们此时需要考虑两个要素， i i i在自己这里选的方案与 i i i的传球方案，显然总方案数是 ∑ i = 0 a i ∑ j = 1 a i [ j > i ] = ( a i + 1 ) a i 2 \sum_{i=0}^{a_{i}}\sum_{j=1}^{a_{i}}[j>i]=\frac{(a_{i}+1)a_{i}}{2} ∑i=0ai​​∑j=1ai​​[j>i]=2(ai​+1)ai​​，也就是 d p i , 0 dp_{i,0} dpi,0​转移的系数。
• d p i , 0 − > d p i + 1 , 1 dp_{i,0}->dp_{i+1,1} dpi,0​−>dpi+1,1​，这里就还需要将 i + 1 i+1 i+1的选球方案加进去，变成 ∑ i = 0 a i ∑ j = 1 a i ∑ k = 1 a i [ j > i ∧ k ⩽ i ] = ∑ i = 0 a i i ( a i − i ) = a i 2 ( a i + 1 ) 2 − a i ( a i + 1 ) ( 2 a i + 1 ) 6 \sum_{i=0}^{a_{i}}\sum_{j=1}^{a_{i}}\sum_{k=1}^{a_{i}}[j>i\wedge k\leqslant i]=\sum_{i=0}^{a_{i}}i(a_{i}-i)=\frac{a_{i}^2(a_{i}+1)}{2}-\frac{a_{i}(a_{i}+1)(2a_{i}+1)}{6} ∑i=0ai​​∑j=1ai​​∑k=1ai​​[j>i∧k⩽i]=∑i=0ai​​i(ai​−i)=2ai2​(ai​+1)​−6ai​(ai​+1)(2ai​+1)​。
• d p i , 1 − > d p i + 1 , 0 dp_{i,1}->dp_{i+1,0} dpi,1​−>dpi+1,0​，显然，这里就只用考虑 i i i的传球方案了，系数就是 a i + 1 a_{i}+1 ai​+1。
• d p i , 1 − > d p i + 1 , 1 dp_{i,1}->dp_{i+1,1} dpi,1​−>dpi+1,1​，这样就要考虑 i i i的传球方案与 i + 1 i+1 i+1的选择方案，系数为 ∑ i = 0 a i ∑ j = 1 a i [ j ⩽ i ] \sum_{i=0}^{a_{i}}\sum_{j=1}^{a_{i}}[j\leqslant i] ∑i=0ai​​∑j=1ai​​[j⩽i]，与第一类是等价的。

有至少传一个球的限制的方案实际上是与这个相似的，很好推出，具体可见代码。
直接这样去 d p 4 dp4 dp4次就可以了，因为还需要枚举第一个人的选球位置，所以要 d p dp dp四次。

时间复杂度 O ( n ) O\left(n\right) O(n)。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;     
const int INF=0x3f3f3f3f;  
const int mo=998244353;
const int inv2=499122177;
const int inv3=332748118;
const int jzm=2333;
const int n1=400;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){putchar('\n');while(x>9){putchar((x%10)|'0');x/=10;}putchar(x|'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,a[MAXN],dp[MAXN][2];
int sum1(int x){return 1ll*x*(x+1)%mo*inv2%mo;}
int sum2(int x){return 1ll*x*(x+1)%mo*(x+x+1)%mo*inv2%mo*inv3%mo;}
int work(int x,int y){
	for(int i=1;i<=n+1;i++)dp[i][0]=dp[i][1]=0;dp[1][y]=1;
	if(x)for(int i=1;i<=n;i++){
		Add(dp[i+1][0],1ll*sum1(a[i])*dp[i][0]%mo,mo);
		Add(dp[i+1][1],1ll*add(1ll*a[i]*sum1(a[i])%mo,mo-sum2(a[i]),mo)%mo*dp[i][0]%mo,mo);
		Add(dp[i+1][0],1ll*(a[i]+1)*dp[i][1]%mo,mo);
		Add(dp[i+1][1],1ll*sum1(a[i])*dp[i][1]%mo,mo);
	}
	else for(int i=1;i<=n;i++){
		Add(dp[i+1][0],1ll*sum1(a[i]-1)*dp[i][0]%mo,mo);
		Add(dp[i+1][1],1ll*add(1ll*a[i]*sum1(a[i])%mo,mo-sum2(a[i]),mo)%mo*dp[i][0]%mo,mo);
		Add(dp[i+1][0],1ll*a[i]*dp[i][1]%mo,mo);
		Add(dp[i+1][1],1ll*sum1(a[i])*dp[i][1]%mo,mo);
	}
	return dp[n+1][y];
}
signed main(){
	read(n);for(int i=1;i<=n;i++)read(a[i]);
	printf("%d\n",((work(1,0)+work(1,1)-work(0,0)-work(0,1))%mo+mo)%mo);
	return 0;
}

谢谢！！！