首先这个期望就是吓唬人的，因为输出格式把期望消掉了
其实就是求总的步数
很容易想到如果通过连边的方式，会出现很多环，每一个环的长度(l_i)就表示这个环里面任意一个点经过(l_i)次变换可以变回它自己
先看一种做法：
假设每一种循环节长度都用到了
我们设每一个环的长度(l_i)，个数(n_i)
假如每一个环里面都有至少一个点被选择了，那么答案就是(lcm(l_1...l_n))
每一位有(n_1+...+n_k)种填法
(k)表示长度不同的环的个数
一共((n_1+...+n_k)^n imes lcm(l_1...l_m))
这个算法对不对？
其实不对。这种方法算出来的答案会大很多
因为这样算，有可能会有没有用到的环
那是不是就需要容斥来消掉不合法的？
怎么容斥？
假设不选(l_1)，每一位有(n_2+...+n_k)种填法，一共有((n_2+...+n_k)^n)种选法
假设不选(l_2)，每一位有(n_1+n_3+...+n_k)种填法，一共有((n_1+n_3+...+n_k)^n)种选法
其他的也是同理，最后把这些不选一种的情况减掉。
发现又减多了，再把不选三种的加上，把不选四种的减去...
这样就能算出k种循环节都被选了的方案数，然后乘上他们的lcm
那么最后的做法就是 状压+容斥
2^k枚举选择哪些循环节长度的字符，把他们都加起来
那么k的范围是多少？
(kleq 14)
因为(1+...+14>100)
总复杂度(O(3^k))
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define inc(a,b) {a+=b;if(a>=mo) a-=mo;}
#define dec(a,b) {a-=b;if(a<0) a+=mo;}
const int maxn=110;
const int mo=1000000007;
int n,m,y[maxn],z[maxn][2],cnt[maxn];
bool vis[maxn];
int gcd(int a,int b)
{
if(!b) return a;
else return gcd(b,a%b);
}
int mul(int a,int b)
{
if(b==0) return 1;
int ans=1;
while (b)
{
if(b&1) ans=1ll*ans*a%mo;
a=1ll*a*a%mo;
b>>=1;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int a=1;a<=m;a++)
scanf("%d",&y[a]);
for(int a=1;a<=m;a++)
if(!vis[a])
{
int p=y[a],num=1;
while (p!=a)
{
vis[p]=true;
p=y[p];
num++;
}
vis[a]=true;
cnt[num]+=num;
}
int q=0;
for(int a=1;a<=m;a++)
if(cnt[a])
{
z[q][0]=a;
z[q][1]=cnt[a];
q++;
}
int ans=0;
for(int a=1;a<(1<<q);a++)
{
int num1=0,lcm=1,v=0;
for (int b=0;b<q;b++)
if (a&(1<<b))
{
num1++;
lcm=lcm*z[b][0]/gcd(lcm,z[b][0]);
}
for(int b=a;b;b=(b-1)&a)
{
int num2=0,lcm=1,total=0;
for(int c=0;c<q;c++)
if(b&(1<<c))
{
num2++;
lcm=lcm*z[c][0]/gcd(lcm,z[c][0]);
total+=z[c][1];
}
if((num1&1)!=(num2&1)) dec(v,mul(total,n))
else inc(v,mul(total,n));
}
inc(ans,1ll*v*lcm%mo);
}
printf("%d
",ans);
return 0;
}