[CSP-S模拟测试]:Cicada与排序（概率DP）

题目传送门（内部题93）

输入格式

　　第一行一个整数$n$，代表数列的长度。
　　接下来一行$n$个数$a_i$，用空格分隔开。

输出格式

　　输出一行$n$个数，表示原数列上这个位置在执行后的期望位置,注意输出的是期望值在$\mod 998244353$下的结果。

数据范围与提示

$n\leqslant 500,1\leqslant a_i\leqslant 10^3$

题解

考虑$DP$，设$dp[i][j][k]$表示在第$i$层下原来的$j$在现在排名为$k$的概率，发现还是不好转移。

再设$g[i][j]$表示在归并排序过程中两个指针分别指向$i,j$的概率，先求出$g$数组，然后直接转移即可。

证明一下时间复杂度，发现每层实际上就是一个卷积，那么复杂度为$T(n)=n^2+2T(\frac{n}{2})$，根据主定理，每层的时间复杂度为$T(n)=n^2$。所以处理单个数的时间复杂度为$\Theta(n^2)$，因为要处理每个数，于是时间复杂度为$\Theta(n^3)$。

时间复杂度：$\Theta(n^3)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

const int mod=998244353;

const int two=499122177;

int n;

int a[501];

long long f[501][501][501],g[501][501],ans;

void merge_sort(int x,int l,int r)

{

	if(l==r){f[x][l][l]=1;return;}

	int mid=(l+r)>>1;

	merge_sort(x+1,l,mid);

	merge_sort(x+1,mid+1,r);

	memset(g,0,sizeof(g));

	g[0][0]=1;

	for(int i=0;i<=mid-l+1;i++)

		for(int j=0;j<=r-mid;j++)

		{

			if(i==mid-l+1)g[i][j+1]=(g[i][j+1]+g[i][j])%mod;

			else if(j==r-mid)g[i+1][j]=(g[i+1][j]+g[i][j])%mod;

			else if(a[i+l]<a[j+mid+1])g[i+1][j]=(g[i+1][j]+g[i][j])%mod;

			else if(a[i+l]>a[j+mid+1])g[i][j+1]=(g[i][j+1]+g[i][j])%mod;

			else

			{

				g[i+1][j]=(g[i+1][j]+g[i][j]*two%mod)%mod;

				g[i][j+1]=(g[i][j+1]+g[i][j]*two%mod)%mod;

			}

		}

	for(int i=l;i<=r;i++)

		for(int j=0;j<=mid-l+1;j++)

			for(int k=0;k<=r-mid;k++)

			{

				if(j==mid-l+1&&k==r-mid)continue;

				if(j==mid-l+1)f[x][i][j+k+l]=(f[x][i][j+k+l]+f[x+1][i][k+mid+1]*g[j][k]%mod)%mod;

				else if(k==r-mid)f[x][i][j+k+l]=(f[x][i][j+k+l]+f[x+1][i][j+l]*g[j][k]%mod)%mod;

				else if(a[j+l]<a[k+mid+1])f[x][i][j+k+l]=(f[x][i][j+k+l]+f[x+1][i][j+l]*g[j][k]%mod)%mod;

				else if(a[j+l]>a[k+mid+1])f[x][i][j+k+l]=(f[x][i][j+k+l]+f[x+1][i][k+mid+1]*g[j][k]%mod)%mod;

				else

				{

					f[x][i][j+k+l]=(f[x][i][j+k+l]+f[x+1][i][k+mid+1]*g[j][k]%mod*two%mod)%mod;

					f[x][i][j+k+l]=(f[x][i][j+k+l]+f[x+1][i][j+l]*g[j][k]%mod*two%mod)%mod;

				}

			}

	sort(a+l,a+r+1);

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

	merge_sort(1,1,n);

	for(int i=1;i<=n;i++)

	{

		ans=0;

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

			ans=(ans+f[1][i][j]*j)%mod;

		printf("%lld ",ans);

	}

	return 0;

}

rp++

巴特西