首页 > 代码库 > P-Function
P-Function
题意:
对于集合 $S = {1, 2, ...., n}$ , 定义函数 $F(x) = y, x, y$ 属于 $S$,对于任何 $x$ 属于 $S$,
有 $F(F...F(x)) = x$, $F$ 出现了 $K$ 次,则这个函数为 $P-function$,问 $P-function$ 的数量。
解法:
注意到 $P-function$ 实质上是 一个 $1$ ~ $n$ 的置换,对于该置换中的所有循环,有 $length | K$。
考虑dp,
$f(i, j)$ 表示考虑前 $i$ 个 $K$ 的因数,确定了 $j$ 个元素的循环形状的方案数。
假定当前循环长度为 $d$,这样考虑每一次决定好 当前剩余最小元素所在的循环。
这样有:
$f(i,j) = \sum{ f(i-1, j-d) C_{j-1}^{d-1} (d-1)!}$
应用滚动数组,复杂度$O(n \sqrt n)$
#include <iostream> #include <cstdio> #include <cstring> #include <vector>> #include <algorithm> #define N 20010 #define P 1000000007LL #define LL long long using namespace std; LL inv[N], f[N], fac[N], rfac[N]; vector<int> Div; LL qpow(LL x,int n) { LL ans = 1; for(;n;n >>= 1, x = x * x % P) if(n & 1) ans = ans * x % P; return ans; } LL comb(int n, int m) { if(n < m) return 0; return fac[n] * rfac[n-m] %P * rfac[m] %P; } int main() { inv[0] = 1; fac[0] = 1; rfac[0] = 1; for(int i = 1;i < N;i++) { fac[i] = fac[i-1] * i % P; inv[i] = qpow(i, P-2); rfac[i] = qpow(fac[i], P-2); } int T, n, K; cin >> T; while(T--) { cin >> n >> K; Div.clear(); for(int i = 1;i*i <= K;i++) if(K % i == 0) { Div.push_back(i); if(i * i != K) Div.push_back(K / i); } sort(Div.begin(),Div.end()); f[0] = 1LL; for(int i = 1;i <= n;i++) { f[i] = 0; for(int j = 0;j < (int)Div.size() && Div[j] <= i;j++) f[i] += f[i - Div[j]] * comb(i - 1, Div[j] - 1) %P * fac[Div[j]-1] %P; f[i] %= P; } cout << f[n] << endl; } return 0; }
P-Function
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。