迭代不动点 / Iterated Fixed Points

ID: 19967

远端评测题

2000ms

512MiB

显示难度省选/NOI−

上传者:

标签>

2026

高校校赛

题目描述

由于评测机性能差异，本题时限调整至 2s。

给定三个整数 $n,k,p$ 。

考虑所有函数

f:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}.

记 $f^k$ 表示函数 $f$ 的 $k$ 次迭代。若 $x\in\{1,2,\ldots,n\}$ 满足

f^k(x)=x,

则称 $x$ 是 $f$ 的一个 $k$ 阶迭代不动点。

求恰好有 $p$ 个 $k$ 阶迭代不动点的函数 $f$ 的数量。答案对 $10^9+7$ 取模。

本题有多组测试数据。

第一行包含一个整数 $T$ $(1\le T\le 10^4)$ ，表示测试数据组数。

接下来 $T$ 行，每行包含三个整数 $n,k,p$ $(1\le n,k\le 10^6,0\le p\le n)$ 。

保证所有测试用例的 $n$ 之和不超过 $10^6$ 。

对于每组测试数据，输出一行一个整数，表示答案对 $10^9+7$ 取模后的结果。