2019.08.25校内模拟赛Graph-白红宇

2019.08.25校内模拟赛Graph

阅读量：5289 次

发布时间：2019-06-14

本文共 1878 字，大约阅读时间需要 6 分钟。

xJ-TEVIzrULURwxOorDvqOssbFGmijj_BkOLbGNT0d4.original.fullsize.png

其实这是道很难的容斥.

所以我考场上直接考虑了\(m=0\)的暴力和白给的\(m=\cfrac{n(n-1)}{2}\)的\(10\)分.

白给的那十分是完全图,根据题意就只需要输出\(0\)就行了.

而至于\(m=0\)的\(40pts\),稍加思索就会发现它和错排是双射关系...

于是,就直接错排就好了.

但我当时忘了错排公式是什么了...递推式也没想起来...

于是我就妄想手推容斥形式的错排,但是我死了,没推出来.

于是我就\(10pts\)走人了.

后来在\(wqy\)的指导下推了出来,长这个亚子:

\[D_n=\sum_{i=0}^n {(-1)^i \left(\begin{array}{c}{i} \\ {n}\end{array}\right) ( n - i ) ! }\]

怎么推出来的呢?

你考虑,强制\(i\)个点的\(p_i=i\),那么方案就是\(\left(\begin{array}{c}{i} \\ {n}\end{array}\right) ( n - i ) !\).

然后我们选出\(i\)个点就行了,这个东西就这亚子出来辽~~

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = a ; i <= b ; ++ i)#define per(i,a,b) for (int i = a ; i >= b ; -- i)#define pii pair < int , int >#define X first#define Y second#define rint read
                
                 #define int long long#define pb push_backusing std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ;template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ;}const int mod = 1e9 + 7 ;const int N = 2e3 + 100 ;int n , m , ans ;int C[N][N] , g[N] ;signed main() { n = rint () ; m = rint () ; g[0] = 1 ; rep ( i , 0 , n ) C[i][0] = 1 ; rep ( i , 1 , n ) g[i] = g[i-1] * i % mod ; rep ( i , 1 , n ) rep ( j , 1 , i ) C[i][j] = ( C[i-1][j-1] + C[i-1][j] ) % mod ; rep ( i , 0 , n ) ans = ( ans + ( ( i & 1 ) ? - 1 : 1 ) * C[n][i] % mod * g[n-i] % mod ) % mod ; printf ("%lld\n" , ans ) ; system ("pause") ; return 0 ;}