Question

2024牛客寒假算法基础集训营1 K 牛镇公务员考试

给出一张试卷有 \(n\) 道单选题，每道题用一个整数 \(a_i\) 和一个长度为 \(5\) 的字符串 \(s_i\) 表示，其中第 \(i\) 道题的题面为：

第 \(a_i\) 道题的答案是 （）

A. \(s_1\)

B. \(s_2\)

C. \(s_3\)

D. \(s_4\)

E. \(s_5\)

问：正确完成全部 \(n\) 道题的答案有多少种

Solution

我们发现第 \(i\) 个问题的答案制约了第 \(a_i\) 个问题的答案，那么显然第 \(a_i\) 个问题的答案也制约着第 \(i\) 个问题的答案

我们利用 \(i\rightarrow a_i\) 的这种关系建边，得到了一个基环树森林，对于每一棵基环树：

• 非环上的节点是没有意义的，因为我们可以从非环链上连接环的那个节点的答案把这条链的答案反推出来
• 对于环上的节点，我们随便令一个节点为起点，暴力枚举 \(A\sim E\)，转一圈下来看看是否满足，那么每棵基环树的方案树就是 \(0\sim 5\)

最后的答案就是所有树的答案相乘

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long LL;
struct node{int x;char s[10];}a[maxn];
const LL TT = 998244353;
vector<int> G[maxn];
int du[maxn],n;
LL ans = 1;

void topo(){
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!du[i]) q.push(i);
    while(!q.empty()){
        int x = q.front(); q.pop();
        du[a[x].x]--;
        if(!du[a[x].x]) q.push(a[x].x);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%*c%s",&a[i].x,a[i].s);
        du[a[i].x]++;
    }
    topo();
    for(int i=1;i<=n;i++) if(du[i]){
        LL now_ans = 0;
        for(int k=0;k<5;k++){
            int p = a[i].x, op = a[i].s[k]-'A';
            while(p != i){
                op = a[p].s[op]-'A', p = a[p].x;
            }
            now_ans += (op == k);
        }
        ans = (ans * now_ans) % TT;
        du[i] = 0;
        for(int p=a[i].x;p!=i;p=a[p].x)
            du[p] = 0;
    }
    printf("%lld\n",ans);
    return 0;
}