[atARC126F]Affine Sort

记$g(k)$为$c$恰为$k$的合法三元组数，显然$f(k)=\sum_{i=1}^{k}g(i)$

结论：若$\lim_{k\rightarrow \infty}\frac{g(k)}{k^{2}}$存在，记其为$s$，则$\lim_{k\rightarrow \infty}\frac{f(k)}{k^{3}}=\frac{1}{3}s$

任取正实数$\epsilon$，根据极限的定义$\exists k_{0}\ge 1$，满足$\forall k\ge k_{0},s-\epsilon\le \frac{g(k)}{k^{2}}\le s+\epsilon$

对其求和并简单变形，不难得到$s-\epsilon\le \frac{\sum_{i=k_{0}}^{k}g(i)}{\sum_{i=k_{0}}^{k}i^2}\le s+\epsilon$

当$k\rightarrow\infty$时，显然中间的式子可以看作$\frac{f(k)}{\frac{1}{3}k^{3}}$，即得证

由此，不妨考虑如何求出$s$，进行如下构造：

定义$[x]$为$x$的小数部分，即$[x]=x-\lfloor x\rfloor$（这里$\lfloor x\rfloor$为小于等于$x$的最大整数）

注意到$x\ mod\ c<y\ mod\ c$当且仅当$[\frac{x}{c}]<[\frac{y}{c}]$，将其代入条件，也即$(aX_{i}+b)mod\ c$严格单调递增当且仅当$[\alpha X_{1}+\beta]<[\alpha X_{2}+\beta]<...<[\alpha X_{n}+\beta]$（其中$\alpha=\frac{a}{c}$且$\beta=\frac{b}{c}$）

考虑$\alpha$和$\beta$，由于$c(=k)\rightarrow \infty$，因此$a,b\in [0,c)$可以看作$\alpha$和$\beta$在$[0,1)$内均匀分布

记$D=\{(\alpha,\beta)\mid \alpha,\beta\in [0,1)$且$[\alpha X_{1}+\beta]<[\alpha X_{2}+\beta]<...<[\alpha X_{n}+\beta]\}$，不妨考虑将$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}$）

对于$\alpha\in [0,1)$，$\exists \beta\in [0,1),(\alpha,\beta)\in D$的必要条件为$\sum_{i=1}^{n}f_{i}(\alpha)=1$（感性理解，即至多只能转一圈）

进一步的，若$\alpha$满足此条件，那么$(\alpha,\beta)\in D$当且仅当$[\alpha X_{1}+\beta]<[\alpha X_{n}+\beta]$（结合前者显然），进而不难得到$\alpha$所在列上黑色部分的长度即为$[(X_{1}-X_{n})\alpha]$

事实上，这里并没有考虑$[\alpha X_{i}+\beta]=[\alpha X_{i+1}+\beta]$的情况，但显然线段并不影响面积

枚举$\lfloor (X_{i+1}-X_{i})\alpha\rfloor$，即将$[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(S\log 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\n",ans);

80     return 0;

81 }

巴特西

[atARC126F]Affine Sort

最新文章

热门文章