• 周日. 9月 25th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[51nod1020]逆序排列

admin

11月 28, 2021

题目链接:

51nod1020

首先考虑设(f[i][j])表示(i)个数的排列有(j)对逆序对的方案数。

那么怎么求(f[i][j])

若有一个(1sim n-1)的排列,那么现在插入(n),那么(n)只会和后面的数产生逆序对(前面的一定比(n)小),也就可以比原来多产生(0sim n-1)对逆序对。

那么有转移方程:(f[i][j]=sum_{k=j-i+1}^j f[i-1][k])

前缀和优化,时间复杂度 (O(nk))

辣鸡题目卡空间?

其实只用求一个前缀和数组,回答时用两个相减得答案。

空间复杂度 (O(nk))

代码:

#include <cstdio>

int t,n,k;
int s[1005][20005];
const int p=1000000007;

int main()
{
	for(register int i=1;i<=1000;++i)
		for(register int j=0;j<=20000;++j)
		{
			if(!j)s[i][j]=1;
			else if(j<i)s[i][j]=s[i-1][j]+s[i][j-1];
			else s[i][j]=(s[i-1][j]-s[i-1][j-i]+p)%p+s[i][j-1];
			if(s[i][j]>=p)s[i][j]-=p;
		}
	for(scanf("%d",&t);t--;)
	{
		scanf("%d%d",&n,&k);
		if(!k)printf("%d
",s[n][k]);
		else printf("%d
",(s[n][k]-s[n][k-1]+p)%p);
	}
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。