题意:长度为 N 的序列,M 种颜色,要求用恰好 K 种颜色为序列染色,且相邻元素颜色不同,求方案数 % 1E9 + 7

容易想到分两步处理,第一步求组合数 C(M, K),从 M 种颜色中确定 K 个要用的。然后将问题转化成用恰好 K 种颜色,给长度为 N 的序列染色,要求相邻两两不同。完成转化之后,我很快想出了一个计数方案:\(K(K - 1)^{n - 1}\),但是这是有问题的,不保证 K 个颜色都被使用过。但是这个结论仍然有助于解题:这个式子的意义是:可以使用 2 至 k 种颜色,但不允许相邻同色的方案数。一个套路是求可以使用 2 至 k - 1 种颜色,但不允许相邻同色,然后与之前相减,得到的就是恰好使用 K 种颜色的方案数。以 K - 1 代换 K,得到:\((K - 1)(K - 2)^{n - 1}\),再次观察和思考,这是用了 K - 1 种颜色,但是不知道是原先 K 种颜色中哪 K - 1 种,而且其中还有交,很自然想到容斥原理。个人是数学苦手,不擅长推,小范围打表验证,并优化若干细节后在 CF Gym 上通过。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

  private static final long MOD = 1000000007;
  private static final long[] reverseRootCache;
  static {
    reverseRootCache = new long[1000001];
    for (int i = 1; i < reverseRootCache.length; i++) {
      reverseRootCache[i] = reverseRoot(i, MOD);
    }
  }

  public static void main(String[] args) {
    new Main().solve();
  }

  private void solve() {
    QuickScanner in = new QuickScanner();
    PrintWriter out = new PrintWriter(System.out);
    int cases = in.nextInt();
    for (int i = 1; i <= cases; i++) {
      int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
      /*
       * Stage one: Choose k color from m colors.
       * 
       * Stage two: Count number of ways to color n elements with exactly k colors, without any 2
       * adjacent element are the same.
       */
      long stateOneAns = getCombinations(m, k)[k];
      long stateTwoAns = workStateTwo(n, k);
      out.printf("Case #%d: %d\n", i, stateOneAns * stateTwoAns % MOD);
    }
    out.flush();
  }

  private long[] getCombinations(int n, int maxK) {
    assert (n > 0 && maxK >= 0 && maxK <= n);
    long[] comb = new long[maxK + 1];
    comb[0] = 1;
    for (int i = 0; i < maxK; i++) {
      comb[i + 1] = comb[i] * reverseRootCache[i + 1] % MOD * (n - i) % MOD;
    }
    return comb;
  }

  private long workStateTwo(int n, int k) {
    long[] comb = getCombinations(k, k);
    long ret = 0;
    long segnum = 1;
    // Inclusion and Exclusion.
    for (int i = k; i > 0; i--) {
      ret += segnum * workRough(n, i) % MOD * comb[i] % MOD;
      ret = (ret + MOD) % MOD;
      segnum *= -1;
    }
    return ret;
  }

  /*
   * A rough counting. Count number of ways to color n elements with 2 ~ k colors, without any 2
   * adjacent element are the same.
   */
  private long workRough(long n, long k) {
    return k * modPow(k - 1, n - 1, MOD);
  }

  private static long modPow(long a, long x, long mod) {
    long ret = 1;
    a %= MOD;
    while (x > 0) {
      if ((x & 1) > 0) {
        ret = (ret * a) % MOD;
      }
      a = a * a % MOD;
      x >>= 1;
    }
    return ret;
  }

  private static long reverseRoot(long x, long mod) {
    return modPow(x, mod - 2, mod);
  }

  private class QuickScanner {
    private BufferedReader bufferedReader = null;
    private StringTokenizer stringTokenizer = null;
    private String nextHolder = null;

    QuickScanner() {
      bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    }

    public String next() {
      // If called hasNext before, should return string in nextHolder.
      if (nextHolder != null) {
        String next = nextHolder;
        nextHolder = null;
        return next;
      }

      try {
        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
          String newLine = bufferedReader.readLine();
          if (newLine != null) {
            stringTokenizer = new StringTokenizer(newLine);
          } else {
            return null;
          }
        }
        return stringTokenizer.nextToken();
      } catch (IOException e) {
        e.printStackTrace();
        return null;
      }
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}

Home