题解：CF288B Polo the Penguin and Houses

· · 题解

不是你们都在写啥啊.jpg

显然不可能有 \exist i\in[1,k],p_i\in(k,n] 或 \exist i\in(k,n],p_i\in[1,k]，不然不可能满足题目要求，所以 [1,k] 和 (k,n] 一定是不连通的，考虑分开它们。

首先考虑比较简单的 (k,n]，显然怎么选 p_i 都是对的，答案为 (n-k)^{n-k}。

然后考虑 [1,k]，显然爆搜能过，考虑求出通项公式。

从 i 向 p_i 连边，这个图应当是一棵环包含 1 的内向基环树。

:::info[我的唐诗做法] 枚举环长 l，选出环有 \binom{k-1}{l-1}(l-1) = \frac{(k-1)!}{(k-l)!} 种，生成树有 lk^{k-l-1} 种（证明见 OI-wiki），于是这个环长对应方案数有 \frac{(k-1)!}{(k-l)!}lk^{k-l-1} 种。

然后我不会求和，我觉得这个要求和基本上就和正确观察思路相同了。（有没有大手子会直接做） :::

感谢 @SalN 和 @CharlieCai 的指点。

:::info[正确的观察] 考虑将这棵基环树拆成一棵以 1 为根的内向树和从 1 出发的一条边，前者方案数为 k^{k-2}，后者方案数为 k，乘起来即可。 :::

于是，这题能够被加强到 n,k\le 1\times 10^{10^7}，具体是使用秦九韶算法分别读出 n\bmod (10^9+7)、n\bmod (10^9+6)、k\bmod (10^9+7) 和 k\bmod (10^9+6)，使用费马小定理即可。

代码，虽然和其他题解都是一样的

:::info[附上搜索代码] 直接搜：

int p[10];
bool pd;
void dfs(int c){
    if(c==k+1){
        for(int i=1,x;i<=k;++i){
            x=i;pd=0;
            for(int j=1;j<=k;++j)x=p[x],pd|=(x==1);
            if(!pd)return;
        }
        ++ans;
        return;
    }
    for(int i=1;i<=k;++i)p[c]=i,dfs(c+1);
}

时间复杂度介于 O(k^{k+1}) 和 O(k^{k+2}) 之间，能过。

根据连通块数量等于环数量的搜索：

int p[10],vis[10];
void dfs(int c){
    if(c==k+1){
        memset(vis,0,sizeof(vis));
        int x=1;
        while(!vis[x])vis[x]=1,x=p[x];
        if(x!=1)return;//判断 1 是否在环上
        for(int i=1;i<=k;++i)
        if(!vis[i]){
            x=i;
            while(!vis[x])vis[x]=i,x=p[x];
            if(vis[x]==i)return;//判断是否产生了新的环，若产生则代表图不连通
        }
        ++ans;
        return;
    }
    for(int i=1;i<=k;++i)p[c]=i,dfs(c+1);
}

时间复杂度为 O(k^{k+1})。 :::