Wuyanru's blog
0%

[PKUWC2024] 排序

发表于 分类于 ，

神奇的状压 dp。

题目链接。

题意

给定了一组希尔排序的步长 ，保证 。

现在需要使用这组步长，给一个 的排列进行排序。

求所有排列中，排序交换次数最大的，进行了多少次交换，以及有多少个排列取得了最大值。

第二问对 取模。

。

。

。

时限 。

题解

考虑从小到大确定每一个数字 填在哪里。

设 分别表示，已经把 这个集合的位置填完了，最大交换次数，以及方案数分别是多少。

枚举当前最小的未填的数字填在 ，考虑需要额外多出多少步。

显然，我们可以把 中的位置都看为 ， 上的数字看作 ，剩余的位置都看作是 。

这样我们就可以逐步模拟额外多出的交换次数了。

对于一个 来说，将所有 的次数算出来，总复杂度是 的。

所以我们的总复杂度是 的，有 分。

考虑排序完 之后，整个序列长什么样。

容易发现，如果我们知道 排完之后序列长什么样，那么我们一定知道序列初始长什么样（一定是同组内倒序排）。

考虑 dp 排完 的状态，考虑合法状态数。

发现同一组内，是 的一定是一段前缀。

所以这样有效状态只有 ，所以复杂度就是 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=1000000007;
int ma[1048600];
ll dp[1048600];
int c1[12][12];
int b[12][31];
int a[31];
int c[31];
int d[15];
int n,m;
inline int get(int sta)
{
    int ans=0;
    for(int i=0;i<d[1];i++)
    {
        int c1=0,c2=0;
        for(int j=i;j<n;j+=d[1])
        {
            c1++;
            if(sta&(1<<j))
            {
                c2++;
                if(c2!=c1) return -1;
            }
        }
        ans=ans*(c1+1)+c2;
    }
    return ans;
}
inline int push(int sta)
{
    for(int i=d[1]-1;i>=0;i--)
    {
        int c=(n-i+d[1]-1)/d[1];
        int p=sta%(c+1);sta/=c+1;
        for(int j=i,now=1;j<n;j+=d[1],now++) a[j]=now<=p;
    }
    memcpy(c,a,sizeof(c));
    for(int i=2;i<=m;i++)
    {
        for(int j=0;j<d[i];j++)
        {
            int c0=0,c1=0;
            for(int k=j;k<n;k+=d[i])
            {
                b[i][k]=c0;
                if(c[k]) c1++;else c0++;
            }
            for(int k=j,now=1;k<n;k+=d[i],now++) c[k]=now<=c1;
            ::c1[i][j]=c1;
        }
    }
    int val=0;
    for(int i=0;i<n;i++) val|=a[i]<<i;
    return val;
}
inline void run(int sta)
{
    int real=push(sta);
    for(int i=0;i<n;i++) if(!a[i]&&get(real|(1<<i))!=-1)
    {
        int val=0,now=i;
        for(int j=2;j<=m;j++)
        {
            val+=b[j][now];
            now=(now%d[j])+c1[j][now%d[j]]*d[j];
        }
        int to=get(real|(1<<i)),v=ma[sta]+val;
        if(v>ma[to]) ma[to]=v,dp[to]=0;
        if(v==ma[to]) dp[to]=(dp[to]+dp[sta])%mod;
    }
}
inline int g1()
{
    int ans=0;
    for(int i=0;i<d[1];i++)
    {
        int c=0;
        for(int j=i;j<n;j+=d[1]) c++;
        ans+=c*(c-1)/2;
    }
    return ans;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        d[i]=read();
        if(d[i]>=n) i--,m--;
    }
    memset(ma,-1,sizeof(ma));
    ma[get(0)]=0,dp[get(0)]=1;

    int N=get((1<<n)-1);
    for(int i=0;i<=N;i++) run(i);
    printf("%d %lld\n",ma[N]+g1(),dp[N]);
    return 0;
}

感谢观看！