题目描述

​　　给你一个\(n\times n\)的方阵\(A\)。定义方阵\(A\)的不动点\((i,j)\)为：\(\forall p,q\geq 0,(A^p)_{i,j}=(A^q)_{i,j}\)

​　　求有多少个元素都在\([0,m)\)之间的\(n\)阶整数方正存在不动点。

​　　对\(10^9+7\)取模。

​　　\(n\leq 3000,m\leq {10}^9\)

题解

​　　我们可以把方阵看成图\(G\)。\(a_{i,j}\)表示第\(i\)个点有多少条有向边连到第\(j\)个点。\(a^p_{i,j}\)表示有多少条从\(i\)出发经过\(p\)条边到达\(j\)的路径。

​　　考虑\(a^0\)，即单位矩阵。所以若不动点\((i,j)\)在主对角线上则\(a_{i,j}=1\)，否则\(a_{i,j}=0\)。

​　　有一个结论：这个方阵有不动点当且仅当这个图不是强连通图。

​　　证明：

​　　　　1.如果\(G\)不是强连通图，那么一定存在一组\((i,j)\)使得\(a^p_{i,j}=0\)。

​　　　　2.如果\(G\)是强连通图，那么一定存在一个\(p\)使得\(a^p_{i,j}\neq 0\)。我们考虑\(a_{i,i}=1\)的情况，因为当\(a_{i,i}>1\)时当\(p=1\)时就不是不动点了。那么存在一个\(p\)使得第\(i\)个点走\(p\)条边回到第\(i\)点有至少两种走法：只走\(i\)->\(i\)，或者在图上走一圈回到\(i\)。所以一定存在一个\(p\)使得\(a^p_{i,i}>1\)。所以方阵不存在不动点。

​　　根据证明1，我们可以忽略自环（有没有自环不影响结果）。

​　　现在我们要求的是\(n\)个点，任意两个点之间可以有\(0\)~\(m-1\)条边，存在多少种不同的非强连通图。

​　　我们设\(f_i=i\)个点组成强连通图的方案数，\(g_{i,j}=i\)个点组成\(j\)个独立的强连通分量的方案数，\(g'_i=\sum_{j=1}^i{(-1)}^{j-1}g_{i,j},h_i=i\)个点组成的有向图个数。

​ 　　先放公式：

​　　在\(g'_i=h_i−Σ_{j=1}^{i−1}(^i_j)m^{j(i−j)}h_{i−j}g'_j\)这个式子中，我们计算\(i\)个点不是相互独立的强连通图的数量，然后用\(h_i\)去减。枚举没有出边的强连通分量的点数之和，然后用容斥计算贡献。对于任意缩完点后DAG中仍然存在边的有向图，出度为\(0\)的强联通分量的点数总和一定小于\(i\)，所以\(j\)从\(1\)枚举到\(i-1\)时能枚举到这些强联通块的所有子集。从而根据\(Σ_{j=0}^i(−1)^j(^i_j)=0\)（\(i\)是强联通块个数），该有向图被完全抵消。对于所有缩完点后联通块彼此独立的有向图(也就是\(g'_i\)要的那些东西)，所有联通块的全集不会被计算到（因为这些联通块个数总和是\(i\)，不在\(1\)到\(i-1\)的枚举范围内），所以会剩下来一项\((^i_i)\)，根据\(\sum_{j=0}^i{(−1)}^j(^i_j)=0,\sum_{j=0}^{i-1}{(−1)}^j(^i_j)={(−1)}^{i−1}(^i_i)={(−1)}^{i−1}\)，这一项的贡献恰好跟\(i\)的奇偶性有关，所以最后得出来的\(g'\)也是带符号的。

​　　在\(f_i=g'_i+\sum_{j=1}^{i-1}(^{i-1}_{j-1})f_jg'_{i-j}\)这个式子中，我们枚举\(1\)所在的强连通分量的点数，算出\(\sum_{j=2}^i{(-1)}^jg_{i,j}\)，然后用\(g'_i\)去加就可以得到\(g_{i,1}\)，也就是\(f_i\)。

​　　最后的答案就是非强连通图的数量乘上自环的贡献，也就是\((h_n-f_n)m^n\)。

　　时间复杂度：\(O(n^2)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

ll p=1000000007;

ll fp(ll a,ll b)

{

	ll s=1;

	while(b)

	{

		if(b&1)

			s=s*a%p;

		a=a*a%p;

		b>>=1;

	}

	return s;

}

ll c[3010][3010];

ll f[3010];

ll g[3010];

ll h[3010];

ll pm[5000010];

int main()

{

	ll n,m;

	scanf("%lld%lld",&n,&m);

	if(m<=1)

	{

		printf("0\n");

		return 0;

	}

	if(n==1)

	{

		printf("1\n");

		return 0;

	}

	int i,j;

	memset(c,0,sizeof c);

	c[0][0]=1;

	for(i=1;i<=n;i++)

	{

		c[i][0]=1;

		for(j=1;j<=i;j++)

			c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;

	}

	for(i=1;i<=n;i++)

		h[i]=fp(m,i*(i-1));

	pm[0]=1;

	for(i=1;i<=n*n/2;i++)

		pm[i]=pm[i-1]*m%p;

	f[1]=1;

	g[1]=1;

	for(i=2;i<=n;i++)

	{

		g[i]=h[i];

		for(j=1;j<i;j++)

			g[i]=(g[i]-c[i][j]*pm[j*(i-j)]%p*h[i-j]%p*g[j]%p)%p;

		f[i]=g[i];

		for(j=1;j<i;j++)

			f[i]=(f[i]+c[i-1][j-1]*f[j]%p*g[i-j]%p)%p;

	}

	ll ans=(h[n]-f[n])*pm[n]%p;

	ans=(ans+p)%p;

	printf("%lld\n",ans);

	return 0;

}