传送门：
http://codeforces.com/problemset/problem/398/E
题解：
首先答案不超过2。
最长环=1时，ans=0
最长环=2时，ans=1
否则，ans=2
考虑有长度大于2的环时如何两步出解。
那么第一步肯定是把大环拆成若干长度不超过2的环。
不妨确定一个x，设它指向y，指向它的是z，那么肯定将y、z交换，这样x、y在一个环里，然后剩下一个len-2的环，不过因为z不能再动了，所以对这个环的拆分就唯一了，一直下去可以把环拆开，并且只考虑这个环的方案数是len。
有多个环时，这些环的选择时可以相交的。
现在有两个环，
一定有一步交换位于不同环上的两个点，如果依然想拆成若干长度不超过2的环，那么剩下的交换也是唯一的。
由于对称问题，也只有len种。
显然两个环的时候必须长度相等才有解。
然后我并不会证更多环没有解。
然后就可以设个(f[i][j])表示长度为i的有j个环的方案数
(f[i][j]=f[i][j-1]*i+f[i][j-2]*(j-1)*i)，复杂度是调和级数
那么接下来(O(k!))暴力的话也TLE了。
考虑确定每个点就是把若干条链拼起来，那么就只用集合划分了。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i < B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int mo = 1e9 + 7;
ll ksm(ll x, ll y) {
ll s = 1;
for(; y; y /= 2, x = x * x % mo)
if(y & 1) s = s * x % mo;
return s;
}
const int N = 1e6 + 5;
int n, k, a[N], r[N], q[N];
ll fac[15];
vector<ll> f[N], nf[N];
int b[N], b0, cnt[N];
int c[N], c0, d[N];
ll ans, sum, s2;
void dg(int x) {
if(x > b0) {
ll s = sum, s3 = s2;
fo(i, 1, c0) {
s3 += c[i] > 2;
s = s * nf[c[i]][cnt[c[i]]] % mo;
cnt[c[i]] ++;
s = s * f[c[i]][cnt[c[i]]] % mo;
}
ll xs = 1;
fo(i, 1, c0) xs = xs * fac[d[i] - 1] % mo;
ans = (ans + (s3 ? s : 1) * xs) % mo;
fo(i, 1, c0) cnt[c[i]] --;
return;
}
fo(i, 1, c0) {
c[i] += b[x];
d[i] ++;
dg(x + 1);
d[i] --;
c[i] -= b[x];
}
c[++ c0] = b[x]; d[c0] = 1;
dg(x + 1);
d[c0] = 0; c0 --;
}
int main() {
freopen("determination.in", "r", stdin);
freopen("determination.out", "w", stdout);
fac[0] = 1; fo(i, 1, 15) fac[i] = fac[i - 1] * i % mo;
scanf("%d %d", &n, &k);
fo(i, 1, n) scanf("%d", &a[i]), r[a[i]] ++;
fo(i, 1, n) {
f[i].resize(n / i + 1);
nf[i].resize(n / i + 1);
f[i][0] = 1;
fo(j, 1, n / i) {
f[i][j] = f[i][j - 1];
if(j >= 2) f[i][j] = (f[i][j] + f[i][j - 2] * (j - 1)) % mo;
f[i][j] = f[i][j] * i % mo;
}
ll s = 1;
fo(j, 1, n / i) s = s * f[i][j] % mo;
s = ksm(s, mo - 2);
fd(j, n / i, 0) nf[i][j] = s, s = s * f[i][j] % mo;
s = 1;
fo(j, 1, n / i) {
nf[i][j] = nf[i][j] * s % mo;
s = s * f[i][j] % mo;
}
}
fo(i, 1, n) if(!r[i]) {
int x = i; q[x] = 1;
b[++ b0] = 0;
do {
b[b0] ++;
x = a[x];
q[x] = 1;
} while(x != 0);
}
fo(i, 1, n) if(!q[i]) {
int x = i, len = 0;
do {
len ++;
x = a[x];
q[x] = 1;
} while(x != i);
cnt[len] ++;
}
sum = 1;
fo(i, 1, n) sum = sum * f[i][cnt[i]] % mo, s2 += cnt[i] * (i > 2);
dg(1);
pp("%lld", ans);
}