题目链接:

题解: 讲一下官方题解的做法: 就是求那个图(官方题解里的)的拓扑序个数，设\(dp[i][j]\)表示有\(i\)个0色和\(j\)个非0色的图的拓扑序个数(\(i<j\))，则转移一是加入一个0色球，二是加入一个非0色球(拓扑序以非0色球开始)，这种情况下我们固定了开头所以还剩\(((K-1)j+i-1)\)个位置放入\((K-2)\)个球，\(dp[i][j]=dp[i-1][j]+dp[i][j-1]\times {

{(K-1)j+i-1}\choose{K-2}}\).

另外有一种反着的做法(我代码写的就是这个)，但是并不懂(曾经懂过但是现在脑子又乱了)

启示: 这种计数很多都是考虑第一个，千万不要惯性思维无脑考虑最后一个！！！

代码

#include
    
     #include
     
      #include
      
       #define llong long longusing namespace std;const int N = 2000;const int P = 1e9+7;llong dp[N+3][N+3];llong fact[5000003],finv[5000003];int n,m;llong quickpow(llong x,llong y){    llong cur = x,ret = 1ll;    for(int i=0; y; i++)    {        if(y&(1ll<
       
        =0; i--) finv[i] = finv[i+1]*(i+1)%P;    scanf("%d%d",&n,&m);    if(m==1) {printf("1"); return 0;}    dp[0][0] = 1ll;    for(int i=1; i<=n; i++)    {        dp[i][0] = 1ll;        for(int j=1; j<=i; j++)        {            dp[i][j] = dp[i-1][j];            dp[i][j] += comb((n-i)+(n-(j-1))*(m-1)-1,m-2)*dp[i][j-1]%P;            dp[i][j] %= P;        }    }    llong ans = dp[n][n]*fact[n]%P;    printf("%lld\n",ans);    return 0;}