题解归档 - cf2239D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2239D
• 本地来源：problems/cf2239D/idea.md
• 题目链接：https://codeforces.com/contest/2239/problem/D
• 原始标题：CF2239D - Hunting the Beast

思路

CF2239D - Hunting the Beast

pattern

Functional graph labeled counting + exponential generating function + Lagrange inversion.

claim

For a fixed functional graph, a starting set is valid iff:

• every vertex with indegree 0 is chosen;
• every component that is only a directed cycle is hit by the set at least once.

Reason: in a component with trees feeding into the cycle, choosing all indegree-0 leaves reaches every tree path and then the whole cycle. A component with no indegree-0 vertex must have every indegree equal to 1, hence is a pure cycle and needs one chosen cycle vertex.

Let z mark chosen vertices and x mark labels. Ordinary rooted tree node weight is z if it has no children, otherwise 1+z, so

T=x(z+(1+z)(exp(T)-1))=x((1+z)exp(T)-1).

A cycle vertex attachment has generating function

R=x(1+z)exp(T)=T+x.

All components are directed cycles of length at least 2. The all-trivial cycle case must subtract the invalid empty choice on that pure cycle, therefore component EGF is

C=sum_{l>=2}((T+x)^l-x^l)/l = log((1-x)/(1-x-T))-T.

Thus the full EGF is

F=exp(C)=exp(-T)(1-x)/(1-x-T).

Using T=x phi(T), phi(u)=(1+z)exp(u)-1, and

F=exp(-T)-x d/dx exp(-T),

for n>=1:

[x^n]F=(n-1)/n [u^{n-1}] exp(-u)((1+z)exp(u)-1)^n.

Extracting [z^m] gives the final answer:

(n-1) * sum_{j=m}^n (-1)^{n-j} C(n,j) C(j,m) (j-1)^{n-1}.

necessary

No self-loop means cycle lengths are at least 2. This is exactly why component cycles start from length 2; the formula also gives 0 for n=1.

sufficient

The EGF enumerates all no-self-loop functional graphs by components and multiplies the exact valid-set polynomial per component, so coefficient [x^n/n! z^m] is the requested sum.

brute/check

For n<=5, enumerated all maps f(i)!=i and all subsets, then compared against the formula:

• 2: 2 1
• 3: 12 18 8
• 4: 72 216 228 81
• 5: 480 2400 4400 3500 1024

The official sample also matches, including n=8,m=3 -> 20415360.

brute.cpp is a definition-level checker for small data (n<=10): enumerate every no-self-loop functional graph and every starting subset by reachability mask. It is only for local/test2 checks, not an accepted solution.

Implementation note: solution.cpp reads all tests first, sorts them by equal n, and reuses the values (j-1)^(n-1) only over the actually queried interval j>=min_m. This never performs more modular exponentiations than the direct formula and is much faster when many tests share the same n. The product is evaluated as

C(n,j) C(j,m) = n! / (m! (n-j)! (j-m)!)

to avoid an extra combination call in the hot loop.

edge

• n=1,m=1: there are no outgoing choices, answer 0.
• m=n: formula remains valid; sample-like small values match (n-1)^n times valid full set behavior.

代码

来源：problems/cf2239D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e7;
const ll mod=998244353;
ll jc[maxn+5],jcn[maxn+5];
ll qmksm(ll a,ll b){
    ll sc=1,zc=a%mod;
    while(b){
        if(b&1) sc=sc*zc%mod;
        b>>=1,zc=zc*zc%mod;
    }
    return sc;
}
ll ny(ll x){
    return qmksm(x,mod-2);
}
ll zhs(ll m,ll n){
    if(m<0 or m>n) return 0;
    return jc[n]*jcn[m]%mod*jcn[n-m]%mod;
}
void pre_cal(){
    ll i;
    jc[0]=1;
    for(i=1;i<=maxn;i++) jc[i]=jc[i-1]*i%mod;
    jcn[maxn]=ny(jc[maxn]);
    for(i=maxn;i>=1;i--) jcn[i-1]=jcn[i]*i%mod;
}
int main(){
    ll t,n,m,j,cur,ans;
    pre_cal();
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        ans=0;
        for(j=m;j<=n;j++){
            cur=zhs(j,n)*zhs(m,j)%mod*qmksm(j-1,n-1)%mod;
            if((n-j)%2==1) ans=(ans-cur+mod)%mod;
            else ans=(ans+cur)%mod;
        }
        ans=ans*(n-1)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}