记$g(k)$为$c$恰为$k$的合法三元组数，显然$f(k)=sum_{i=1}^{k}g(i)$
结论：若$lim_{k ightarrow infty}frac{g(k)}{k^{2}}$存在，记其为$s$，则$lim_{k ightarrow infty}frac{f(k)}{k^{3}}=frac{1}{3}s$
任取正实数$epsilon$，根据极限的定义$exists k_{0}ge 1$，满足$forall kge k_{0},s-epsilonle frac{g(k)}{k^{2}}le s+epsilon$
对其求和并简单变形，不难得到$s-epsilonle frac{sum_{i=k_{0}}^{k}g(i)}{sum_{i=k_{0}}^{k}i^2}le s+epsilon$
当$k ightarrowinfty$时，显然中间的式子可以看作$frac{f(k)}{frac{1}{3}k^{3}}$，即得证
由此，不妨考虑如何求出$s$，进行如下构造：
定义$[x]$为$x$的小数部分，即$[x]=x-lfloor x floor$（这里$lfloor x floor$为小于等于$x$的最大整数）
注意到$x mod c<y mod c$当且仅当$[frac{x}{c}]<[frac{y}{c}]$，将其代入条件，也即$(aX_{i}+b)mod c$严格单调递增当且仅当$[alpha X_{1}+eta]<[alpha X_{2}+eta]<...<[alpha X_{n}+eta]$（其中$alpha=frac{a}{c}$且$eta=frac{b}{c}$）
考虑$alpha$和$eta$，由于$c(=k) ightarrow infty$，因此$a,bin [0,c)$可以看作$alpha$和$eta$在$[0,1)$内均匀分布
记$D={(alpha,eta)mid alpha,etain [0,1)$且$[alpha X_{1}+eta]<[alpha X_{2}+eta]<...<[alpha X_{n}+eta]}$，不妨考虑将$D$中的点都染上黑色，此时问题即求黑色部分的面积
将$[0,1)$看成一个圆（顺时针方向为增大），并定义$f_{i}(alpha)$为$[alpha X_{i}]$到$[alpha X_{i+1}]$在圆上顺时针方向的距离，那么不难得到$f_{i}(alpha)=[(X_{i+1}-X_{i})alpha]$（特别的，定义$X_{n+1}=X_{1}$）
对于$alphain [0,1)$，$exists etain [0,1),(alpha,eta)in D$的必要条件为$sum_{i=1}^{n}f_{i}(alpha)=1$（感性理解，即至多只能转一圈）
进一步的，若$alpha$满足此条件，那么$(alpha,eta)in D$当且仅当$[alpha X_{1}+eta]<[alpha X_{n}+eta]$（结合前者显然），进而不难得到$alpha$所在列上黑色部分的长度即为$[(X_{1}-X_{n})alpha]$
事实上，这里并没有考虑$[alpha X_{i}+eta]=[alpha X_{i+1}+eta]$的情况，但显然线段并不影响面积
枚举$lfloor (X_{i+1}-X_{i})alpha floor$，即将$[0,1)$划分为$o(|X_{i+1}-X_{i}|)$段，每一段的$f_{i}(alpha)$都是关于$alpha$的一次函数，那么考虑$sum_{i=1}^{n}f_{i}(alpha)$即是一个$o(sum_{i=1}^{n}|X_{i+1}-X_{i}|)$段的一次函数
对于其中一段，若其截距为1（不难发现斜率必然为0），那么即对$[(X_{1}-X_{n})alpha]$求一个区间定积分，将其的端点也加入后同样变为一次函数，直接计算即可
时间复杂度为$o(Slog S)$（其中$S=sum_{i=1}^{n}X_{i}$），可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1005 4 #define mod 998244353 5 #define inv2 499122177 6 #define inv3 332748118 7 #define ll long long 8 #define fi first 9 #define se second 10 int qpow(int n,int m){ 11 int s=n,ans=1; 12 while (m){ 13 if (m&1)ans=(ll)ans*s%mod; 14 s=(ll)s*s%mod; 15 m>>=1; 16 } 17 return ans; 18 } 19 struct Frac{ 20 int a,b; 21 Frac(){ 22 a=0,b=1; 23 } 24 Frac(int aa,int bb){ 25 int g=__gcd(aa,bb); 26 a=aa/g,b=bb/g; 27 } 28 bool operator < (const Frac &k)const{ 29 return (ll)a*k.b<(ll)b*k.a; 30 } 31 int get_val(){ 32 return (ll)a*qpow(b,mod-2)%mod; 33 } 34 }; 35 struct Line{ 36 int k,b; 37 Line(){ 38 k=b=0; 39 } 40 Line(int kk,int bb){ 41 k=kk,b=bb; 42 } 43 int get_int(Frac x){ 44 int s=x.get_val(); 45 return (((ll)inv2*k%mod*s%mod*s+(ll)b*s)%mod+mod)%mod; 46 } 47 int get_int(Frac x,Frac y){ 48 return (get_int(y)-get_int(x)+mod)%mod; 49 } 50 }; 51 vector<pair<Frac,int> >v; 52 int n,s,ans,a[N]; 53 int main(){ 54 scanf("%d",&n); 55 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 56 a[n+1]=a[1]; 57 for(int i=1;i<=n;i++){ 58 if (a[i]==a[i+1])continue; 59 if (a[i]<a[i+1]){ 60 for(int j=1;j<a[i+1]-a[i];j++)v.push_back(make_pair(Frac(j,a[i+1]-a[i]),-1)); 61 } 62 else{ 63 for(int j=0;j<a[i]-a[i+1];j++)v.push_back(make_pair(Frac(j,a[i]-a[i+1]),1)); 64 } 65 } 66 v.push_back(make_pair(Frac(1,1),0)); 67 sort(v.begin(),v.end()); 68 for(int i=0,j=0;i<v.size();i++){ 69 if ((i)&&(v[i-1].fi<v[i].fi)){ 70 if (s==1){ 71 if (a[1]>a[n])ans=(ans+Line(a[1]-a[n],-j).get_int(v[i-1].fi,v[i].fi))%mod; 72 else ans=(ans+Line(a[1]-a[n],j+1).get_int(v[i-1].fi,v[i].fi))%mod; 73 } 74 } 75 s+=v[i].se; 76 while (!(v[i].fi<Frac(j+1,abs(a[1]-a[n]))))j++; 77 } 78 ans=(ll)inv3*ans%mod; 79 printf("%d ",ans); 80 return 0; 81 }