[atARC113F]Social Distance

（由于是实数范围，端点足够小，因此区间都使用中括号，且符号取等号）

定义$P(X)$表示$\forall 2\le i\le n,a_{i}-a_{i-1}\ge X$的概率，那么我们所求的也就是$P(X)$的积分

考虑如何求某一个$P(X)$（$X$为非负实数）：

令$a'_{i}=a_{i}-iX$，那么也就是要求$\forall 2\le i\le n,a'_{i-1}\le a'_{i}$，之后$a'_{i}$随机区间为$[x_{i-1}-iX,x_{i}-iX]$

将所有端点排序并后，依次为$p_{1}\le p_{2}\le ...\le p_{2n}$，那么这个问题也就是离散的了，再记$[l_{i},r_{i}]$为$a'_{i}$所对应的区间，则可以通过如下dp来计算：

$f_{i,j}$表示仅考虑$a'_{1},a'_{2},...,a'_{i}$，满足$a'_{1}\le a'_{2}\le ...\le a'_{i}\le p_{j}$的概率，转移枚举$k$满足$a_{k-1}\le p_{i-1}\le a_{k}$，之后从$f_{k-1,j-1}$转移过来，下面考虑转移系数：

若不满足$\forall k\le t\le i,[p_{j-1},p_{j}]\subseteq [l_{t},r_{t}]$则为0，否则即$\frac{\prod_{k\le t\le i}\frac{p_{j}-p_{j-1}}{r_{t}-l_{t}}}{(i-k+1)!}$，通过倒序枚举$k$可以方便维护

综上，就可以$o(n^{3})$求出$P(X)$

如果$p_{i}$的相对顺序不变，那么结果即一个关于$X$的多项式，同样可以dp求出

又因为只有$(2n)^{2}$个交点，因此只有$o(n^{2})$种顺序，对于确定的顺序后解出$X$的范围并求积分即可

另外dp状态中需要存储一个$n$次多项式，因此时间复杂度是$o(n^{6})$

还有由于最后答案是对998244353取模，需要用分数的形式存储交点以及比较

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 25

  4 #define M 1000005

  5 #define mod 998244353

  6 int n,ans,x[N],inv[M];

  7 struct frac{

  8     int x,y;

  9     bool operator < (const frac k)const{

 10         return x*k.y<k.x*y;

 11     }

 12     frac operator + (const frac k)const{

 13         return frac{x*k.y+k.x*y,y*k.y};

 14     }

 15     frac operator - ()const{

 16         return frac{-x,y};

 17     }

 18     frac operator * (const frac k)const{

 19         return frac{x*k.x,y*k.y};

 20     }

 21     int get_val(){

 22         return 1LL*x*inv[y]%mod;

 23     }

 24 }l[N],r[N];

 25 vector<frac>v;

 26 struct poly{

 27     int n,a[N];

 28     bool operator < (const poly k)const{

 29         return n<k.n;

 30     }

 31     poly operator + (const poly k)const{

 32         poly o;

 33         o.n=max(n,k.n);

 34         for(int i=0;i<=min(n,k.n);i++)o.a[i]=(a[i]+k.a[i])%mod;

 35         for(int i=k.n+1;i<=n;i++)o.a[i]=a[i];

 36         for(int i=n+1;i<=k.n;i++)o.a[i]=k.a[i];

 37         return o;

 38     }

 39     poly operator - ()const{

 40         poly o;

 41         o.n=n;

 42         for(int i=0;i<=n;i++)o.a[i]=mod-a[i];

 43         return o;

 44     }

 45     poly operator * (int k)const{

 46         poly o;

 47         o.n=n;

 48         for(int i=0;i<=n;i++)o.a[i]=1LL*a[i]*k%mod;

 49         return o;

 50     }

 51     poly operator * (poly k)const{

 52         poly o;

 53         o.n=n+k.n;

 54         for(int i=0;i<=o.n;i++)o.a[i]=0;

 55         for(int i=0;i<=n;i++)

 56             for(int j=0;j<=k.n;j++)o.a[i+j]=(o.a[i+j]+1LL*a[i]*k.a[j])%mod;

 57         return o;

 58     }

 59     poly dx(){

 60         poly o;

 61         o.n=n+1,o.a[0]=0;

 62         for(int i=0;i<=n;i++)o.a[i+1]=1LL*inv[i+1]*a[i]%mod;

 63         return o;

 64     }

 65     int get_val(int k){

 66         int s=1,ans=0;

 67         for(int i=0;i<=n;i++){

 68             ans=(ans+1LL*s*a[i])%mod;

 69             s=1LL*s*k%mod;

 70         }

 71         return ans;

 72     }

 73 }one,f[N][N<<1];

 74 pair<frac,poly>a[N<<1];

 75 int main(){

 76     one.n=0,one.a[0]=1;

 77     inv[0]=inv[1]=1;

 78     for(int i=2;i<M-4;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

 79     scanf("%d",&n);

 80     for(int i=0;i<=n;i++)scanf("%d",&x[i]);

 81     for(int i=0;i<=n;i++)

 82         for(int j=0;j<i;j++){

 83             if (i!=j)v.push_back(frac{x[i]-x[j],i-j});

 84             if (i-1!=j)v.push_back(frac{x[i]-x[j],i-j-1});

 85             if ((j)&&(i!=j-1))v.push_back(frac{x[i]-x[j],i-j+1});

 86         }

 87     sort(v.begin(),v.end());

 88     frac lst=frac{0,1};

 89     for(int i=0;i<v.size();i++)

 90         if (lst<v[i]){

 91             frac mid=frac{lst.x+v[i].x,lst.y+v[i].y};//通过mid来比较

 92             for(int j=0;j<=n;j++){

 93                 poly o;

 94                 o.n=1,o.a[0]=x[j];

 95                 if (j){

 96                     o.a[1]=mod-j;

 97                     a[2*j-1]=make_pair(frac{x[j],1}+(-frac{j,1}*mid),o);

 98                 }

 99                 if (j<n){

100                     o.a[1]=mod-(j+1);

101                     a[2*j]=make_pair(frac{x[j],1}+(-frac{j+1,1}*mid),o);

102                 }

103             }

104             sort(a,a+2*n);

105             for(int j=0;j<2*n;j++)f[0][j]=one;

106             for(int j=1;j<=n;j++){

107                 l[j]=frac{x[j-1],1}+(-frac{j,1}*mid);

108                 r[j]=frac{x[j],1}+(-frac{j,1}*mid);

109                 for(int k=1;k<2*n;k++){

110                     f[j][k]=f[j][k-1];

111                     poly s=one;

112                     for(int t=j;t;t--){

113                         if ((a[k-1].first<l[t])||(r[t]<a[k].first))break;

114                         s=s*(1LL*inv[x[t]-x[t-1]]*inv[j-t+1]%mod);

115                         s=s*(a[k].second+(-a[k-1].second));

116                         f[j][k]=f[j][k]+s*f[t-1][k-1];

117                     }

118                 }

119             }

120             poly s=f[n][2*n-1].dx();

121             ans=((ans+s.get_val(v[i].get_val()))%mod+mod-s.get_val(lst.get_val()))%mod;

122             lst=v[i];

123         }

124     printf("%d",ans);

125 }

巴特西

[atARC113F]Social Distance

最新文章

热门文章