前言
这题补了一万年，终于过了。
模拟赛撞原题不会可太艹了
题目
题目大意：
给定一个整数 (N) 表示人数，接下来给出序列 (A)，(A_i) 表示第 (i) 个人拥有的球的数量。
这 (N) 个人坐成一个环，接下来他们会同时给右边那个人自己的一部分球(当然可以全给或者不给)，记操作后的序列为 (S)，定义其权值 (f(S)=prod S_i)，求所有不同的 (S) 的权值和，答案对 (998244353) 取模。
(3le Nle 10^5;0le A_ile 10^9.)
讲解
解题前的热身
首先不要把题目想错了，每个人给的球数量不同并不一定等同于最后的 (S) 序列不同。
然后我们挖掘性质：如果每个人都至少给出了一个球，其实可以让每个人都少给相同的个数，效果相同，所以至少有一个人没给球。
从简单入手
考虑最暴力的 dp，令 (dp_{i,j}) 表示第 (i) 个人给 (j) 个球的前缀乘积和，然后我们指定 (i) 不给球，为了不算重，需要指定他前面的人必须给球。
然后我们就有了一个 (O(n^2A_i^2)) 的超高效做法(注意我并没有把指定给球或不给球体现在转移方程中)：
最后只需要把所有的 (dp_{i,0}) 累加起来即可。
优化1
这时间复杂度看上去非常恐怖，但事实上它完全可以优化：
可以发现只需求出 (sum_{l=0}^{a_{j-1}}dp_{j-1,l} imes l) 和 (sum_{l=0}^{a_{j-1}}dp_{j-1,l} imes (a_j-k)) 即可完成转移，可以简单优化为 (O(n^2A_i))。
优化2
既然我们已经发现可以维护上面那两个东西就完成转移，我们令：
不难写出转移(其实是把草稿本的内容抄过来)：
注：(lr(x)=frac{(1+x) imes x}{2},lr2(x)=frac{x imes (x+1) imes (2x+1)}{6})，分别对应 (1) 次和 (2) 次的求和公式。
此时我们需要累加的就是 (f(i-1) imes a_i+g(i-1))。
现在时间复杂度已经优化到了 (O(n^2))。
优化3
到这一步其实已经很简单了，用矩阵转移相当方便，分别维护一下前后缀即可。
时间复杂度 (O(n))。
代码
附赠草稿纸的代码
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int MOD = 998244353;
const int inv2 = (MOD+1) >> 1;
const int inv6 = 166374059;
int N,ans;
int a[MAXN];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
LL lr(LL x){return (x+1) * x % MOD * inv2 % MOD;}
LL lr2(LL x){return x * (x+1) % MOD * (2*x+1) % MOD * inv6 % MOD;}
struct Matrix
{
int n,m,a[2][2];
Matrix(){memset(a,0,sizeof(a));}
Matrix operator * (const Matrix &C)const{
Matrix ret; ret.n = n; ret.m = C.m;
for(int i = 0;i < n;++ i)
for(int k = 0;k < m;++ k)
if(a[i][k])
for(int j = 0;j < C.m;++ j)
ret.a[i][j] = (ret.a[i][j] + 1ll * a[i][k] * C.a[k][j]) % MOD;
return ret;
}
void print()
{
putchar('
');
for(int i = 0;i < n;++ i,putchar('
'))
for(int j = 0;j < m;++ j)
Put(a[i][j],' ');
}
}pre[MAXN],suf[MAXN],I,A,tt;
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
I.n = I.m = 2; I.a[0][0] = I.a[1][1] = 1;
N = Read();
tt = pre[0] = suf[N+1] = I;
for(int i = 1;i <= N;++ i) a[i] = Read();
for(int j = 1;j <= N;++ j)
{
pre[j].n = pre[j].m = 2;
pre[j].a[0][0] = (1ll*a[j]*a[j]-lr(a[j])) % MOD;
pre[j].a[1][0] = a[j];
pre[j].a[0][1] = (lr(a[j])*a[j]-lr2(a[j])) % MOD;
pre[j].a[1][1] = lr(a[j]);
if(j > 1 && j < N) tt = tt * pre[j];
pre[j] = pre[j-1] * pre[j];
}
for(int j = N;j >= 1;-- j)
{
suf[j].n = suf[j].m = 2;
suf[j].a[0][0] = ((a[j]+1ll)*a[j]-lr(a[j])) % MOD;
suf[j].a[1][0] = (a[j]+1)%MOD;
suf[j].a[0][1] = (lr(a[j])*a[j]-lr2(a[j])) % MOD;
suf[j].a[1][1] = lr(a[j]);
suf[j] = suf[j] * suf[j+1];
}
A.n = 1;A.m = 2;
for(int i = 1;i <= N;++ i)
{
int i1 = i+1; if(i1 > N) i1 = 1;
A.a[0][0] = lr(a[i1]); A.a[0][1] = (lr(a[i1]) * a[i1] - lr2(a[i1])) % MOD;
if(i1 < i) A.a[0][0] = (A.a[0][0] - a[i1] + MOD) % MOD;
if(i+2 <= N) A = A * suf[i+2];
if(i^N) A = A * pre[i-1];
else A = A * tt;
ans = (ans + A.a[0][1] + 1ll * a[i] * A.a[0][0]) % MOD;
}
Put((ans+MOD)%MOD,'
');
return 0;
}
/*
如果过了把 define int LL 删了
现在已经是 O(n^2) 啦，下午来套个矩阵就过了！
好家伙，现在到晚上了
sum i * (x-i) = ix - i^2 = lr(x)x - lr2(x)
搞错啦搞错啦，
应该是枚举一个不给，前面枚举过的都必给
f(j) = sum(k) dp[j][k]
g(j) = sum(k) dp[j][k] * k
dp[j][k] += dp[j-1][l] * (a[j] - k + l) lin[0,a[j-1]]
dp[j][k] = g(j-1) - k * f(j-1) + a[j] * f(j-1)
f(j) = sum(k:(j<i)~a[j]) g(j-1) - k * f(j-1) + a[j] * f(j-1)
= (a[j]-(j<i)+1) * g(j-1) - lr(a[j]) * f(j-1) + (a[j]-(j<i)+1) * a[j] * f(j-1)
= (a[j]-(j<i)+1) * (g(j-1) + a[j] * f(j-1)) - lr(a[j]) * f(j-1)
pre
f g
a[j]*a[j]-lr(a[j]) lr(a[j])*a[j]-lr2(a[j])
a[j] lr(a[j])
g(j) = sum(k:(j<i)~a[j]) (g(j-1) - k * f(j-1) + a[j] * f(j-1)) * k
= sum(k:(j<i)~a[j]) k * g(j-1) - k^2 * f(j-1) + k * a[j] * f(j-1)
= lr(a[j]) * g(j-1) - lr2(a[j]) * f(j-1) + lr(a[j]) * a[j] * f(j-1)
= lr(a[j]) * (g(j-1) + a[j] * f(j-1)) - lr2(a[j]) * f(j-1)
dp[j][0] = g(j-1) - a[j] * f(j-1)
suf
f g
(a[j]+1)*a[j]-lr(a[j]) lr(a[j])*a[j]-lr2(a[j])
a[j]+1 lr(a[j])
*/
总结
有些题的 dp 可以由相当暴力的转移方程优化得到正解，然而我们要怎么确定这条路一定走得通呢？
这道题的特点是最初 (j,k,l) 转移的时候 (k,l) 其实并没有恐怖地揉在一起，使得我们有将其拆开的机会。
后来定义 (f,g) 的时候我们是发现其实并不需要这么多状态，只需要整体即可，故可以整体转移。
当然还是要多做题找经验。
我没有暗示水子哥。