[C++知识库]codeforce1670C. Where is the Pizza?

传送门：今天想不出骚话

定义一个长度为n的序列为：序列中仅包含数字1到n，且序列中没有相同的数字，也就是说1到n每个数字必须出现一次。

现在有两个序列a和b，把这两个序列重新排列，仍然可以构成一个序列，称为c。
重新排列的方式为：$c[i]=a[i]$ 或 $c[i]=b[i]$
且已知部分位置上序列c的值

求有多少种方式能构成满足条件的序列c

首先来考虑，当确定了序列c的一位后，影响范围会有多大。
假设有如下序列，序列c第一位选定为$a[0]$
不难得知，选择1之后，将决定第二位是2，第三位是3。由于$b[2]=1$，且1已经选定位置，所以不会再影响其他，故影响范围确定。
如果第一位选择2，影响范围相同。所以该部分只能为序列c提供两种不同排列方式。

我们不妨以$a[i]$为起点，$b[i]$为终点，构建有向边。在该影响范围内可以构成一个环。

不难看出，环与环之间没有影响，各自独立的为序列c提供2种不同排列。所以，如果不对序列c进程干预，那么排列数应当是$2^{sum}$，其中sum为环的个数。

但是题目中对c的选择进行了干预，被干预位置没有自由选择的权力，因此不适合构建有向边。根据c的干预结果对有向图进行调整，删除部分边后重新计数，就是序列c的排列数

至于怎么判断是不是环，可以dfs，也可以并查集，不会建议百度

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define Pair pair<int,int>
#define re return

#define getLen(name,index) name[index].size()
#define mem(a,b) memset(a,b,sizeof(a))
#define Make(a,b) make_pair(a,b)
#define Push(num) push_back(num)
#define rep(index,star,finish) for(register int index=star;index<finish;index++)
#define drep(index,finish,star) for(register int index=finish;index>=star;index--)
using namespace std;

template<class T> void _deb(const char *name,T val){
    cout<<name<<val<<endl;
}

const int MAXN = 1e5+5;
const int MOD = 1e9+7;

int t,n;
int storeA[MAXN],storeB[MAXN];
int store[MAXN];
ll mPow[MAXN];
int dsu[MAXN];
inline int getRoot(int x);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    mPow[0] = 1;
    rep(i,1,100000) {
        mPow[i] = mPow[i-1] * 2LL;
        mPow[i] = mPow[i] % MOD;
    }

    scanf("%d",&t);
    while(t--) {
        scanf("%d", &n);

        rep(i,0,n+1)
            dsu[i] = i;

        rep(i,0,n)
            scanf("%d", storeA+i);
        rep(i,0,n)
            scanf("%d", storeB+i);
        rep(i,0,n)
            scanf("%d", &store[i]);

        int ans = 0;
        // build path
        rep(i,0,n) {
            if(store[i])
                continue;
            int commonA = storeA[i];
            int commonB = storeB[i];
            if(commonA == commonB)
                continue;
            int rootA = getRoot(commonA);
            int rootB = getRoot(commonB);
            if(rootA == rootB){
                // loop
                ans ++;
            }else{
                dsu[rootA] = rootB;
            }
        }
        printf("%lld\n", mPow[ans]);
    }

    re 0;
}
inline int getRoot(int x) {
    if(dsu[x] == x)
        return x;
    return dsu[x] = getRoot(dsu[x]);
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖