bzoj2776

问长度为n的全排列中,有多少个排列经过k轮冒泡排序可以排好……
排序框架:

i从n-1到1循环
(一轮的开始)
 j从1到i循环
    如果a[j]>a[j+1]
      交换a[j]和a[j+1]
(一轮的结束)

update

应人要求……已经补上推导

SOLUTION

群众喜闻乐见的计数题……不算太难
不明为啥bzoj上过的人这么少……除了root就只有colrko和我……
这题的计数和冒泡排序有关……
最近的清华集训也有一道……
简单说一下做法吧……

首先观察性质:
对于排列a[]
如果a[i]< i,a[i]这个数每一轮都会前进一个位置……
那么这个数前进i-a[i]次才可能会到达它应该到的位置……
所以一个排列a[],它需要的冒泡排序的轮数x
满足x=max{i-a[i]}
这样看起来就可做了……

我们要统计这样的全排列个数——

max{i-a[i]}=k for 1<=i<=n

这样子就可以手推公式了……

容易发现公式是……

需要高精度……
于是上python……
由于好久没用……都忘记怎么读入了……
因为写成了

n,k=raw_input().split("")

而怒wa一发……太,b了……

update on 2014/3/6

因为已经有超过两个人来问我这题怎么推了……
我可以告诉大家其实结论是我找规律找到的……
不过对着结论我还是能给大家证明一下的……
2333
定义f(n,k)为满足i-a[i]<=k,for 1<=i<=n的排列个数
那么答案显然为f(n,k)-f(n,k-1)
下面推f(n,k)的封闭形式……
我们首先注意到对于序列的前k+1个元素……它们的取值无论是多少都无所谓……
因为它们的限制相当于a[i]>=1……
所以我们可以考虑先在[k+2,n]这后n-k-1个位置放数字放出一个合法方案后再来随便放前面的
我们先考虑第n个位置的可能取值……因为a[n]>=n-k……所以a[n]的可能取值个数为k+1个
那么我们放好第n个位置的数字了之后,第n-1个位置能放的数字的集合是哪些呢?
因为a[n-1]>=n-k-1,而且a[n]!=a[n-1],显然a[n]>=n-k-1……所以在放好a[n]后,a[n-1]可能的取值个数为k+1个。
同理下去……对于a[i],在所有a[i+1]\a[i+2]\a[i+3]...\a[n]都填好数字之后……它的可能取值个数为k+1个
那么[k+2,n]这n-k-1个位置放数字的合法方案个数自然是(k+1)^(n-k-1)
然后前k+1个位置可以随便放,所以整个数列的个数为(k+1)!*(k+1)^(n-k-1)

所以

证明完毕lol

Comments

comments powered by Disqus