即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

jzoj 5086. 【GDOI2017第四轮模拟day1】数列 搜索+meet in the middle

编程语言 qq_33229466 8℃ 0评论
本文目录
[隐藏]

1.题意

有一个长度为n 的排列,现在有一些位置的数已经模糊不清了,你只知道这个排列的逆序对个数是K,你能计算出总共有多少可能的排列吗?


n <=10^3,K<=10^9,0 的个数不超过14。

2.分析

考场上就只往状压和容斥上想了,没想到meet in the middle。


只要分成两部分然后分别求全排列,最后用一个桶记录即可。

3.代码

#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;

const int N=20;

int n,m,tot,g[N],f[N],h[N],vis[1005],a[1005],c[N][N],ret[N],pos[N],use[N],tim,w[15005];
LL ans;

void dfs2(int x,int y)
{
    if (x>y)
    {
        int s=0;
        for (int i=1;i<=y;i++)
        {
            s+=c[g[i]][i]+g[i]-1;
            for (int j=1;jif (g[j]>g[i]) s++;
            for (int j=1;j<=y;j++)
                if (g[j]return;
    }
    for (int i=1;i<=y;i++)
        if (!vis[i])
        {
            g[x]=f[i];vis[i]=1;
            dfs2(x+1,y);
            vis[i]=0;
        }
}

void dfs3(int x,int y)
{
    if (x>y)
    {
        int s=0;
        for (int i=1;i<=y;i++)
        {
            s+=c[g[i]][i+n/2];
            for (int j=1;jif (g[j]>g[i]) s++;
        }
        if (s<=m) ans+=w[m-s];
        return;
    }
    for (int i=1;i<=y;i++)
        if (!vis[i])
        {
            g[x]=h[i];vis[i]=1;
            dfs3(x+1,y);
            vis[i]=0;
        }
}

void solve()
{
    memset(w,0,sizeof(w));
    dfs2(1,n/2);
    int s=0;
    for (int i=1;i<=n/2;i++) vis[f[i]]=1;
    for (int i=1;i<=n;i++) if (!vis[i]) h[++s]=i;
    for (int i=1;i<=n/2;i++) vis[f[i]]=0;
    dfs3(1,s);
}

void dfs1(int x,int last)
{
    if (x==n/2)
    {
        solve();
        return;
    }
    for (int i=last+1;i<=n;i++)
        if (!use[i])
        {
            use[i]=1;f[x+1]=i;
            dfs1(x+1,i);
            use[i]=0;
        }
}

int main()
{
    freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if (!a[i]) pos[++tot]=i;
        else vis[a[i]]=1;
    }
    for (int i=1,s=0;i<=n;i++) if (!vis[i]) ret[++s]=i;
    for (int i=1;iif (a[i])
            for (int j=i+1;j<=n;j++)
                if (a[j]&&a[j]for (int i=1;i<=tot;i++)
        for (int j=1;j<=tot;j++)
        {
            for (int k=1;kif (a[k]>ret[i]) c[i][j]++;
            for (int k=pos[j]+1;k<=n;k++) if (a[k]&&a[k]memset(vis,0,sizeof(vis));
    dfs1(0,0);
    printf("%lld",ans);
    return 0;
}

转载请注明:CodingBlog » jzoj 5086. 【GDOI2017第四轮模拟day1】数列 搜索+meet in the middle

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情