Codeforces986B [Petr and Permutations]

看到两个随机的swap次数，很容易想到跟奇偶性有关。然后就凉了。赛后思考了一下，这个思路应该没问题，那就需要考虑swap的奇偶性与排列的关系。因此，我们考虑如何把两个不相邻数的swap，转换为相邻的数的swap，以便于利用逆序数进行推导。假设swap(a[x],a[y])，可以转化为把a[y]向左移动，一直换到x这个位置，再把现在位于x+1这个位置上的a[x]向右移动一直换到y这个位置。显然这个过程一共做了(y-x) + (y-(x+1)) = 2*(y-x)-1次交换，每次交换逆序数的变化的绝对值为1，那么对于一次交换逆序数的变换一定为奇数。那么显然，一个排列的初始逆序数都为0，如果最终的逆序数为奇数，则一定进行了奇数次交换，否则进行了偶数次交换，那结论就很明显了：只要最终的逆序数与某种方式swap次数奇偶性一致，答案就是这种方式。看别人代码发现不用求逆序数，只要求出一种交换方案的，交换次数再判断奇偶性就行了，复杂度比较优秀，用上面的结论，也很好证明，我这里还是用的逆序数的方法，可以过。

#include 
     
      typedef long long ll;const int N = 1e6 + 100;using namespace std;int n,a[N],ans=0;int B[N];int ask(int x){    int ans=0;    for(int i=x;i;i-=(i&(-i)))ans+=B[i];    return ans;}void add(int x,int v) {    for(int i=x;i<=n;i+=(i&(-i)))B[i]+=v;}int main() {    scanf("%d",&n);    for(int i=1;i<=n;++i) {        scanf("%d",&a[i]);        ans+=(ask(n)-ask(a[i]));        add(a[i],1);    }    if((ans&1)==((3*n)&1))puts("Petr");    else puts("Um_nik");    return 0;}
     

Codeforces986C [AND Graph]

一个01串与它有边的01串，就是它的补集的所有子集。对于m个01串暴力计算它的补集的所有子集，如果某个子集出现在这m个串里，就继续暴力计算这个数所有子集的补集。状态数只有2^22搜索的复杂度有保证。（为啥想不到？

#include 
     
      #define rep(i,a,b) for(int i=a;i<=b;++i)typedef long long ll;const int N = (1<<23);using namespace std;int n,m,a[N],vis[N],in[N],ans;void dfs(int s) {    if(vis[s])return;    vis[s]=1;    if(in[s])dfs((1<