AT_abc313_g

· · 题解

本文同步发表于我的博客。

前置知识：【模板】类欧几里得算法

读题，我们发现 a 的顺序不影响答案，所以先排序。

然后发现，先做一次操作二，再做一次操作一，序列是不变的，所以有效的操作序列一定是 A 次操作一然后 B 次操作二。

接着我们设做完所有操作一后的序列为 a'，设 a'_k=0 且 a'_{k+1}=a_{k+1}-A 满足 a_k< A \le a_{k+1}，那么这个时候最多可以做 \lfloor\frac{(n-k)A+\sum_{i=1}^k a_i}{n}\rfloor 次操作二，而每次操作二得到的序列都不同。也就是对于所有 a_k< A \le a_{k+1}，我们能得到的序列个数为：

\sum_{A=a_k+1}^{a_{k+1}} (\lfloor\frac{(n-k)A+pre_k}{n}\rfloor+1)=\sum_{i=1}^{a_{k+1}-a_k} \lfloor\frac{(n-k)i+[(n-k)a_k+pre_k]}{n}\rfloor+a_{k+1}-a_k

类欧算即可。记得要单独算只做 0\sim a_1 次的情况，此时做操作二是无效操作，所以是 a_1+1 种序列。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int A[200005],pre[200005];
int calc(int n,int a,int b,int c){
    int m=(a*n+b)/c;
    if(!a) return (n+1)*(b/c)%mod;
    if(a<c&&b<c)return (m*n+mod-calc(m-1,c,c-b-1,a))%mod;
    return (n*(n+1)/2%mod*(a/c)+(n+1)*(b/c)+calc(n,a%c,b%c,c))%mod;
}
int n,ans;
signed main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>A[i];
    sort(A+1,A+1+n);
    ans=A[1]+1,pre[1]=A[1];
    for(int i=2;i<=n;i++){
        ans+=calc(A[i]-A[i-1],n-i+1,(n-i+1)*A[i-1]+pre[i-1],n)-((n-i+1)*A[i-1]+pre[i-1])/n+A[i]-A[i-1];
        pre[i]=pre[i-1]+A[i];
    }
    cout<<(ans%mod+mod)%mod<<endl;
    return 0;
}