组合数+容斥原理 UVALive 7040 Color(14西安F)-白红宇

组合数+容斥原理 UVALive 7040 Color(14西安F)

阅读量：5833 次

发布时间：2019-06-18

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

题意：n盆花涂色，相邻不能涂相同的颜色，从m中颜色选取k种颜色涂，保证正好有k种颜色

分析：从m中颜色选取k种就是C (m, k)，然后第一个有k种选择，之后的都有k-1种选择，这样是不超过k种颜色的方案，那么减去少了Ai颜色的方案数，用容斥原理，最后答案是C(m,k) × ( k × (k-1)^(n-1) + ∑((-1)^p × C(k, p) × p × (p-1)^(n-1) ) (2 <= p <= k-1)；

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e6 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const int EPS = 1e-8;int inv[N];void init(int n) { inv[1] = 1; for (int i=2; i<=n; ++i) { inv[i] = (MOD - MOD / i) * 1ll * inv[MOD%i] % MOD; //inv[n] }}int pow_mod(int x, int n, int p) { int ret = 1; while (n) { if (n & 1) ret = ret * 1l * x % p; x = x * 1ll * x % p; n >>= 1; } return ret;}int f(int n, int k) { if (!k) return 0; else return k * 1ll * pow_mod (k-1, n-1, MOD) % MOD;}int main(void) { init (1000000); int T, cas = 0; scanf ("%d", &T); while (T--) { int n, m, k; scanf ("%d%d%d", &n, &m, &k); ll ans = 0; int res = 1; for (int i=1; i<=k; ++i) { res = res * 1ll * (k - i + 1) % MOD * inv[i] % MOD; if (k - i & 1) { ans -= res * 1ll * f (n, i) % MOD; if (ans < 0) ans += MOD; } else { ans += res * 1ll * f (n, i) % MOD; if (ans >= MOD) ans -= MOD; } } for (int i=1; i<=k; ++i) { ans = ans * 1ll * (m - i + 1) % MOD * inv[i] % MOD; } printf ("Case #%d: %lld\n", ++cas, ans); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4852200.html

你可能感兴趣的文章