题目大意

题意:现在有 $n$ 个格子和 $m$ 种颜色,问你恰好将这些花盆染成 $k$ 种颜色,且同种颜色不相邻的方案数。答案对 $10^9+7$ 取模, $n,m, \leq 10^9,k \leq 10^6$

心路历程

首先比较 sb 的交了个 $\binom m k k(k-1)^{n-1}$,WA on 2(其实就 $2$ 组数据)...
然后仔细思考一下,发现 $k(k-1)^{n-1}$ 貌似是 $\leq k$ 的??然后我就叫了个 $\binom m k (k(k-1)^{n-1}-(k-1)(k-2)^{n-1})$,WA on 2
稍微理性分析了一下发现这样算太 naive 了,然后改了一下 就 A 了。(今天真是意识模糊的一天)

题解

首先我们来分析一下第二种方法为什么不对:考虑在 $k(k-1)^{n-1}$ 中使用了 $x$ 种颜色的某一种确定的方案被计算的次数:$\binom k x$。显然 $\binom k x - \binom {k-1} x \neq 1$,所以做法萎了。
于是我重新推了一下式子。。发现设 $f_i$ 表示恰好染 $i$ 种颜色的方案,$g_i$ 表示染了 $\leq i$ 中颜色的方案的话,首先 $g_i = i(i-1)^{n-1}$,然后发现它们之间有关系
$$g_n = \sum_{k = 1}^n \binom n i f_i$$
于是立刻有
$$f_n = \sum_{k=i}^n (-1)^{n-i} \binom n i g_i$$
我们要求的答案就是 $\binom m k f_k$
科普小学知识1:暴力算组合数的复杂度是 $O(m)$ 的,可以使用广义定义 $\binom n m = \frac{n^{\underline m}}{m!}$
科普小学知识2:组合数可以快速算一行。(这个算幼儿园知识了吧我就不说了)
所以这题就是个很 ez 的题了。

/*
 * Author: RainAir
 * Time: 2019-08-27 19:22:27
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int ha = 1e9 + 7;
const int MAXN = 1e6 + 5;

inline int qpow(int a,int n=ha-2){
    if(a < 0) return 0;
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int cs,n,m,k,f[MAXN];// (m,*)

inline void prepare(){
    f[0] = 1;f[1] = k;
    FOR(i,2,k) f[i] = 1ll*f[i-1]*(k-i+1)%ha*qpow(i)%ha;
    f[k] = 1;
}

int C(int n,int m){
    if(n < m) return 0;
    if(!m) return 1;
    int ans = 1,t = 1;
    FOR(i,n-m+1,n) ans = 1ll*ans*(i%ha)%ha;
    FOR(i,1,m) t = 1ll*t*i%ha;
    return 1ll*ans*qpow(t)%ha;
}

inline void Solve(){
    printf("Case #%lld: ",++cs);
    scanf("%lld%lld%lld",&n,&m,&k);
    prepare();int ans = 0;
    FOR(i,1,k){
        ans = (ans + ((f[i]*i%ha*qpow(i-1,n-1)%ha)*((k-i)&1 ? -1 : 1)) + ha)%ha;
    }
    printf("%lld\n",ans*C(m,k)%ha);
}

signed main(){
    int T;scanf("%lld",&T);
    while(T--) Solve();
    return 0;
}

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/802/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏