2018宁夏邀请赛I题 bubble sort（思维题

https://vjudge.net/problem/Gym-102222I

居然补到个防ak，刚开始不知道啥是循环左移右移（只能移一次），不好想。。

题意：以冒泡排序为背景给你n,k 问在1~n的n个数的全排列中有几个能经过k次遍历就排好序了（这里排好序是指最长上升子序列长度至少为n-1

for(int i=1;i<n;++i) if(a[i]>a[i+1]) swap(a[i],a[i+1]) 这算一次遍历
结果%mod（也给出来了

题解：冒泡k趟之后，新序列的第i项是原序列前min(i+k,n)项中未在新序列前i-1项中出现过的最小值。新序列的LIS>=n-1相当于在序列1，2，...，n中选择至多一个区间循环左移或右移。

于是可以枚举新序列，算出每个新序列元素在原序列中可能的位置个数，利用乘法原理计算方案数。

模拟下1,2,3,4,5，假设k=1

bit[4]=2^4是12345对应的原序列数量，此时就是sorted

接下来看almost sorted，

左移时，区间长度是2，3，4，假设len=2的话21345,13245,12435，len=3的话23145,13425...

右移时，2重复了不用算，3,4算一下就行了。

最后由于后k个已经定了，刚才算的原串数量还要扩倍。。例如k=2只算了12345没算12354...

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int T,n,k,mod;

LL bit[55];

int main()

{

    scanf("%d",&T);

    for (int z=1;z<=T;++z)

    {

        scanf("%d%d%d",&n,&k,&mod);

        printf("Case #%d: ",z);

        if (k>=n)

        {

            LL ans=1;

            for (int i=1;i<=n;++i) ans=ans*i%mod;

            printf("%lld\n",ans);

            continue;

        }

        bit[0]=1;

        for (int i=1;i<=n;++i) bit[i]=1LL*bit[i-1]*(k+1)%mod;

        LL ans=0;

        //sorted

        ans=bit[n-k];

        //left shift

        for (int len=2;len<=n-k;++len)

            ans+=1LL*(n-k-len+1)*bit[n-k-1]%mod,ans%=mod;

        //right shift

        for (int len=3;len<=n-k;++len)

            ans+=1LL*(n-k-len+1)*bit[n-k-len+1]%mod,ans%=mod;

        //last k

        for (int i=1;i<=k;++i) ans=ans*i%mod;

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

2018宁夏邀请赛I题 bubble sort（思维题

最新文章

热门文章