Comet OJ

Stella981
• 阅读 1298

题意

https://www.cometoj.com/contest/52/problem/C?problem_id=2416

思路

这里提供一种容斥的写法(?好像网上没看到这种写法)

题目要求编号为 $i$ 的节点不能放在 $p_i$ 位置,那我们不妨假设没有这些条件,然后再用二进制容斥的方法减去不满足条件的情况(即固定某些 $i$ 在 $p_i$ 上,这样会好考虑问题一点)。

然后我们面临的问题就是,计算 $A$(二进制)这些数不能选,$B$(二进制)这些位置不能填的方案数。我们枚举两个数,计算它们的对答案的贡献。设小的数为 $i$ ,大的数为 $j$ ,下面分四种情况讨论:

  • $i,j$ 的位置均已确定

    若 $p_i>p_j$ ,则造成 $(j-i)(p_i-p_j)(n-cnt_A)!$ 的贡献( $cnt_A$ 为 $A$ 的二进制中 $1$ 的个数)。

  • $j$ 的位置已经确定

    $i$ 能选的位置为 $\setminus A$( $A$ 对全集取补),尝试让 $\setminus A$ 与 $j$ 匹配,只有 $\setminus A$ 中大于 $j$ 的数才能得配,匹配结果是这个数减 $j$ 。设 $\setminus A$ 所有数的总匹配结果为 $t$ ,它对答案的贡献即为 $(j-i)t(n-cnt_A-1)!$

  • $i$ 的位置已经确定

    与上一种其实没什么区别,只是 $i$ 去匹配 $\setminus A$ 罢了。

  • $i,j$ 的位置均未确定

这次是一个集合匹配一个集合,在外面通过情况二来预处理。假设总匹配结果为 $t$ ,对答案的贡献即为 $(j-i)t(n-cnt_A-2)$

要注意固定数时如果有两个数共用了一个位置(即 $p$ 相等),那这个贡献就直接为 $0$ 了。

代码

#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
#define lowbit(x) ((x)&-(x))
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
int cnt[(1<<16)+5],bin[(1<<16)+5],sum[(1<<16)+5];
int Sum[(1<<16)+5];
ll fac[18];
int n,p[18];

ll f1(int S,int pos)
{
    S=(S|((1<<(pos+1))-1))^((1<<(pos+1))-1);
    return sum[S]-cnt[S]*pos;
}

ll f2(int pos,int S)
{
    S=S&((1<<pos)-1);
    return cnt[S]*pos-sum[S];
}

ll solve(int A,int B)
{
    ll ans=0;
    FOR(i,0,n-1)FOR(j,i+1,n-1)
    {
        if((A>>i&1)&&(A>>j&1))
        {
            if(p[i]>p[j])
                ans+=(j-i)*(p[i]-p[j])*fac[n-cnt[A]];
        }
        else if(!(A>>i&1)&&(A>>j&1))
        {
            ans+=(j-i)*f1(((1<<n)-1)^B,p[j])*fac[n-cnt[A]-1];
        }
        else if((A>>i&1)&&!(A>>j&1))
        {
            ans+=(j-i)*f2(p[i],((1<<n)-1)^B)*fac[n-cnt[A]-1];
        }
        else ans+=(j-i)*Sum[((1<<n)-1)^B]*fac[n-cnt[A]-2];
    }
    return ans;
}
 
int main()
{
    fac[0]=1;FOR(i,1,16)fac[i]=fac[i-1]*i;
    FOR(i,1,1<<16)cnt[i]=cnt[i^lowbit(i)]+1;
    FOR(i,2,1<<16)bin[i]=bin[i>>1]+1;
    FOR(i,1,1<<16)sum[i]=sum[i^lowbit(i)]+bin[lowbit(i)];
    FOR(i,1,1<<16)Sum[i]=Sum[i^lowbit(i)]+f1(i^lowbit(i),bin[lowbit(i)]);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        FOR(i,0,n-1)scanf("%d",&p[i]),p[i]--;
        ll ans=0;
        FOR(i,0,(1<<n)-1)
        {
            int S=0;
            bool flg=1;
            FOR(j,0,n-1)if(i>>j&1)
            {
                if(S&(1<<p[j]))
                {
                    flg=0;
                    break;
                }
                S|=1<<p[j];
            }
            if(!flg)continue;
            if(cnt[i]&1)ans-=solve(i,S);
            else ans+=solve(i,S);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Codeforces Round #565 (Div. 3) C. Lose it!
链接:https://codeforces.com/contest/1176/problem/C(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fcodeforces.com%2Fcontest%2F1176%2Fproblem%2FC)题意:Youare
Stella981 Stella981
3年前
CF 833 B. The Bakery
B.TheBakeryhttp://codeforces.com/contest/833/problem/B(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fcontest%2F833%2Fproblem%2FB)题
Stella981 Stella981
3年前
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法参考文章:(1)Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.codeprj.com%2Fblo
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这