题解：P12215 [蓝桥杯 2023 国 Python B] 困局

· · 题解

这边是题目传送门喵！

欢迎来博客园阅读喵！

这篇是首篇题解吗？

前言：

你们觉得 0<k<\min(n,8) 还是人类的语言吗？

题意

其实题目本身也挺清楚的，不过要注意的点是：既然每一个传送门都只能被使用一次，那么每个传送门都被使用就是恰好 2k 次，因此至少传送 2k 次就是恰好传送 2k 次，也就是每一个传送门都使用了一次。

思路

考虑样例，发现如果两个传送门之间有空地，那么这一块空地应该是对行走路线毫无影响的：一定会走过去而在这个过程中不发生传送。我知道这是一句废话，但是这启示我们直接将空地给拿掉，也就是先从 n = 2k 的情况入手。

只要我能解决这个问题，然后就只用给这 2k 个传送门排位置就可以了也就是答案乘上 \binom{n}{2k} 就可以了。

你们觉得 0<k<\min(n,8) 还是人类的语言吗？

那我岂不是直接对每一个 k 打表算出 n=2k 的答案就写完了？其实就是的。

实际上，鉴于数据范围这么小，可以直接搜索。

至于搜索的过程，我们用一个函数模拟行走的过程，把传送门作为一条边，然后每次把不同的建边的方案丢进去跑就可以了。具体模拟的方法还是看代码吧。

当然，打表也是完全可以的。

代码

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define rloop(i,a,b) for(int i=(a);i>=(int)(b);i--)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=1e6+5;
const ll mod=998244353;

int n,k;
ll cnt[15],ans;
int a[15];
bool vis[15];

int qmi(int a,int k){
    int res=1;
    while(k){
        if(k&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        k>>=1;
    }
    return res;
}

ll calc(int n,int m){ // 组合数计算
    if(m<0||m>n)return 0;
    m=min(m,n-m);
    ll x=1,y=1;
    loop(i,1,m){
        x=1ll*x*(n-i+1)%mod;
        y=1ll*y*i%mod;
    }
    return 1ll*x*qmi(y,mod-2)%mod; // x/y
}

bool check(int k){ // 模拟
    int t=2*k;
    memset(vis,0,sizeof(vis));
    int x=0,cnt=0;
    while(++x<=t){
        if(a[x]&&!vis[x]){
            vis[x]=1;
            x=a[x];
            cnt++;
        }
    }
    return cnt>=2*k; // cnt==2*k
}

void dfs(int u,int k){
    int t=2*k;
    while(u<=t&&a[u])u++;
    if(u>t){
        if(check(k))ans++;
        return;
    }
    loop(v,u+1,t){
        if(!a[v]){
            a[u]=v;a[v]=u; // 建边
            dfs(u+1,k);
            a[u]=a[v]=0;  // 断边
        }
    }
}

void init(){
    cnt[0]=1;
    loop(k,1,7){
        memset(a,0,sizeof(a));
        ans=0;
        dfs(1,k);
        cnt[k]=ans;
    }
    // loop(k,1,7)cout<<cnt[k]<<' ';
    // cout<<'\n';
    // 这一段其实输出的就是打表的结果。
    return;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    init();
    cin>>n>>k;
    if(2*k>n)cout<<"0\n";
    else cout<<1ll*calc(n,2*k)*cnt[k]%mod<<"\n";
    return 0;
}

完结撒花！