Favorite formula:

• Formula 1:

  \(\large f(n) = \displaystyle\sum^n_{k=0}\dbinom{n}{k}g(k) \\ \large \Rightarrow g(n) = \displaystyle\sum^n_{k=0}\left(-1\right)^{n - k}\dbinom{n}{k}f(k)\)

• Formula 2 (at most and exactly):

  \(\large f(n) = \displaystyle\sum^n_{k=m}\dbinom{n}{k}g(k) \\ \large \Rightarrow g(n) = \displaystyle\sum^n_{k=m}\left(-1\right)^{n - k}\dbinom{n}{k}f(k)\)

• Equation 3 (at least with the exact problem):

  \(\large f(n) = \displaystyle\sum^m_{k=n}\dbinom{k}{n}g(k) \\ \large \Rightarrow g(n) = \displaystyle\sum^m_{k=n}\left(-1\right)^{k - n}\dbinom{k}{n}f(k)\)

Example:

• \(\ tt BZOJ\ 2839 \) set count:

  Meaning:

  Given \ (n \) elements, there are \ (2^n \) sets. Now take out several sets from these \ (2^n \) sets so that the number of elements in their intersection is \ (K \), and find the number of schemes of the method. Mold \ (10 ^ 9 + 7 \).

  Data range: \ (n \leq 10^6 \).

  Idea:

  Definition \ (f(x) \) means that there are \ (x \) elements in the intersection set that are fixedly selected, and the number of schemes randomly selected by the remaining elements (without duplication). Definition \ (g(x) \) means that there are exactly \ (x \) elements in the intersection, then:
  \(\large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k) = \dbinom{n}{x}\left(2^{2^{n - x}} - 1\right)\)

  \(\large g(x) = \displaystyle\sum^n_{k = x}(-1)^{k - x}\dbinom{n}{k}f(k)\)

  The answer is \ (g(K) \).

  Time complexity \ (\ Theta\left(n\right) \).

  code:

  Click to view the code

  // =============================================
  // The horizontal line, the victory, and the carving!
  // Author: Sasebo Shiyu
  // Blog: https://www.cnblogs.com/SasebonoShigure
  // =============================================
  
  #include <cstdio>
  #include <iostream>
  
  using namespace std;
  
  typedef long long LL;
  
  const int Maxn = 2e6 + 10;
  const LL Mod = 1000000007;
  
  int n, k;
  LL Answer, Pow = 2;
  LL Fact[Maxn], Inv[Maxn];
  
  inline LL Qkpow (LL Base, LL x) {
  	LL Pow = 1;
  
  	while (x ) {
  		if (x & 1 ) {
  			Pow = Pow * Base % Mod;
  		}
  
  		x >>= 1, Base = Base * Base % Mod;
  	}
  
  	return Pow;
  }
  
  inline LL Getinv (const LL Num) {
  	return Qkpow (Num, Mod - 2);
  }
  
  inline LL Getbinom (const int n, const int m) {
  	return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod;
  }
  
  signed main () {
  	scanf ("%d %d", &n, &k), Fact[0] = 1;
  
  	for (int i = 1; i <= n; ++ i ) {
  		Fact[i] = Fact[i - 1] * i % Mod;
  	}
  
  	Inv[n] = Getinv (Fact[n]);
  
  	for (int i = n - 1; ~i; -- i ) {
  		Inv[i] = Inv[i + 1] * (i + 1) % Mod;
  	}
  
  	for (int i = n, Tag = ((n - k) & 1) ? -1 : 1; i >= k; -- i, Tag = -Tag, Pow = Pow * Pow % Mod ) {
  		Answer = (Answer + Tag * Getbinom (i, k) * Getbinom (n, i) % Mod * (Pow - 1) % Mod + Mod) % Mod;
  //		printf ("%d\n")
  	}
  
  	printf ("%lld\n", Answer);
  	return 0;
  }
  

• \(\ tt BZOJ\ 3422 \) there is nothing to fear:

  Meaning:

  There are \ (n \) candies and \ (n \) tablets. Pair them in pairs. Every candy and pill has an energy value. Find the number of schemes in which the energy of candy is greater than that of tablets, and there are just \ (k \) pairs more than that of tablets. Mold \ (10 ^ 9 + 7 \).
  Data range: \ (n \leq 2 \times 10^3 \)\ (0 \leq k \leq n\). The energy values of tablets and candy are in the range of int, and \ (2n \) energy values are guaranteed to be different from each other.

  Idea:

  Definition \ (f(x) \) means that after the energy of \ (x \) pair of candy is greater than that of pill pairing, the remaining \ (n - x \) pairs of candy and pill are matched randomly (without weight removal), and \ (g(x) \) means that the energy of \ (x \) pair of candy is greater than that of pill pairing, then:

  \(\large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k)\)

  \(\large g(x) = \displaystyle\sum^n_{k=x}\left(-1\right)^{k - x}\dbinom{k}{x}f(k)\)

  The next goal is to find the expression of \ (f(x) \). (excluding \ (g(x) \))

  Obviously we need \ (DP \).

  First, we rank sweets and tablets from small to large in energy value. Definition \ (dp_{i,j} \) means that after the \ (I \) candy is paired, the energy of \ (J \) candy is greater than that of tablet pairing. By definition, we can quickly get \ (\ large dp_{i,j} = dp_{i - 1,j} + \left(tot_i - j + 1\right)dp_{i - 1, j - 1} \), where \ (tot_i \) represents the number of tablets with energy value less than candy \ (I \).

  So, \ (\ large f(x) = dp_{n,x} \cdot \left(n - x\right)! \), the answer is \ (g\left(\dfrac{n+k}{2}\right) \).

  Time complexity \ (\ theta \ left (n ^ 2 \ right \).

  code:

  Click to view the code

  // =============================================
  // The horizontal line, the victory, and the carving!
  // Author: Sasebo Shiyu
  // Blog: https://www.cnblogs.com/SasebonoShigure
  // =============================================
  
  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  
  using namespace std;
  
  typedef long long LL;
  
  const LL Mod = 1e9 + 9;
  const int Maxn = 2e3 + 10;
  
  int n, k, N;
  int A[Maxn], B[Maxn];
  LL Answer;
  LL f[Maxn][Maxn], Fact[Maxn], Inv[Maxn];
  
  inline LL Qkpow (LL Base, LL x) {
  	LL Pow = 1;
  
  	while (x ) {
  		if (x & 1 ) {
  			Pow = Pow * Base % Mod;
  		}
  
  		x >>= 1, Base = Base * Base % Mod;
  	}
  
  	return Pow;
  }
  
  inline LL Getinv (const LL Num) {
  	return Qkpow (Num, Mod - 2);
  }
  
  inline LL Getbinom (const int n, const int m) {
  	return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod;
  }
  
  signed main () {
  	scanf ("%d %d", &n, &k), N = (n + k) >> 1, Fact[0] = 1;
  
  	if ((n + k) & 1 ) {
  		printf ("0\n");
  		return 0;
  	}
  
  	for (int i = 1; i <= n; ++ i ) {
  		Fact[i] = Fact[i - 1] * i % Mod;
  	}
  
  	Inv[n] = Getinv (Fact[n]);
  
  	for (int i = n - 1; ~i; -- i ) {
  		Inv[i] = Inv[i + 1] * (i + 1) % Mod;
  	}
  
  	for (int i = 1; i <= n; ++ i ) {
  		scanf ("%d", A + i);
  	}
  
  	for (int i = 1; i <= n; ++ i ) {
  		scanf ("%d", B + i);
  	}
  
  	sort (A + 1, A + n + 1);
  	sort (B + 1, B + n + 1);
  	f[0][0] = 1;
  
  	for (int i = 1, Count; i <= n; ++ i ) {
  		Count = 0, f[i][0] = f[i - 1][0];
  
  		for (int j = 1; j <= n; ++ j ) {
  			Count += A[i] > B[j];
  		}
  
  		for (int j = 1; j <= i; ++ j ) {
  			f[i][j] = (f[i - 1][j] + max (0, Count - j + 1) * f[i - 1][j - 1] % Mod) % Mod;
  		}
  	}
  
  	for (int i = N, Tag = 1; i <= n; ++ i, Tag = -Tag ) {
  		Answer = (Answer + Tag * Getbinom (i, N) * f[n][i] % Mod * Fact[n - i] % Mod + Mod) % Mod;
  	}
  
  	printf ("%lld\n", Answer);
  	return 0;
  }
  

• \(\ tt BZOJ4665 \) small w candy:

  Meaning:

  Xiao w bought a total of \ (n \) pieces of candy and sent them to \ (n \) individuals. Each candy has a kind. At this time, Xiao w had a whim. If these \ (n \) individuals exchanged sugar with each other, how many schemes would there be to make the types of sugar in each person's hands different from the original. The two schemes are different if and only if there is a person whose type of sugar is different in the two schemes.

  Data range: \ (type_i \leq n \leq 2 \times 10^3 \).

  Idea:

  Goo Goo

  code:

  Click to view the code

  // =============================================
  // The horizontal line, the victory, and the carving!
  // Author: Sasebo Shiyu
  // Blog: https://www.cnblogs.com/SasebonoShigure
  // =============================================
  
  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  
  using namespace std;
  
  typedef long long LL;
  
  const LL Mod = 1e9 + 9;
  const int Maxn = 2e3 + 10;
  
  int n, x;
  int Count[Maxn];
  LL Answer;
  LL f[Maxn][Maxn], Fact[Maxn], Inv[Maxn];
  
  inline LL Qkpow (LL Base, LL x) {
  	LL Pow = 1;
  
  	while (x ) {
  		if (x & 1 ) {
  			Pow = Pow * Base % Mod;
  		}
  
  		x >>= 1, Base = Base * Base % Mod;
  	}
  
  	return Pow;
  }
  
  inline LL Getinv (const LL Num) {
  	return Qkpow (Num, Mod - 2);
  }
  
  inline LL Getbinom (const int n, const int m) {
  	return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod;
  }
  
  signed main () {
  	scanf ("%d", &n), Fact[0] = 1;
  
  	for (int i = 1; i <= n; ++ i ) {
  		scanf ("%d", &x), ++ Count[x];
  	}
  
  	for (int i = 1; i <= n; ++ i ) {
  		Fact[i] = Fact[i - 1] * i % Mod;
  	}
  
  	Inv[n] = Getinv (Fact[n]);
  
  	for (int i = n - 1; ~i; -- i ) {
  		Inv[i] = Inv[i + 1] * (i + 1) % Mod;
  	}
  
  	f[0][0] = 1;
  
  	for (int i = 1; i <= n; ++ i ) {
  		for (int j = 0; j <= n; ++ j ) {
  			for (int k = 0; k <= Count[i] and k <= j; ++ k ) {
  				f[i][j] = (f[i][j] + f[i - 1][j - k] * Getbinom (Count[i], k) % Mod * Inv[Count[i] - k] % Mod) % Mod;
  			}
  
  		}
  	}
  
  	for (int i = 0, Tag = 1; i <= n; ++ i, Tag = -Tag ) {
  		Answer = (Answer + Tag * f[n][i] % Mod * Fact[n - i] % Mod + Mod) % Mod;
  	}
  
  	printf ("%lld\n", Answer);
  	return 0;
  }
  

• \(\tt CF285E\ Positions\ in\ Permutations\) :

  Meaning:

  The perfect number of permutations of a \ (1 \) ∼ \ (n \) is called how many \ (I \) satisfy \ (\ left|P_i - i\right| = 1 \).
  Find how many permutations with length \ (n \) and perfect number exactly \ (m \). The answer is to mold \ (10 ^ 9 + 7 \).

  Data range: \ (1 \leq n \leq 1000 \), \ (0 \leq m \leq n \).

  Idea:

  The definition of \ (f(x) \) means that it is forced to determine that \ (x \) positions are perfect, and the remaining \ (n - x \) positions are placed randomly (without de duplication), and \ (g(x) \) is the number of schemes with exactly \ (x \) positions as perfect. Then there are:

  \(\large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k)\)

  \(\large g(x) = \displaystyle\sum^n_{k=x}\left(-1\right)^{k - x}\dbinom{k}{x}f(k)\)

  Next, we try to get \ (f(x) \).

  The definition \ (dp_{i,j,0/1,0/1} \) indicates that the \ (I \) bit is currently selected. A total of \ (j \) positions are perfect. Whether \ (I \) has been selected and whether the number of schemes of \ (i + 1 \) has been selected.

  According to the definition, we can conduct classified discussion:

  • Bit \ (i \) is perfect:

    • Bit \ (i \) selects \ (i - 1 \):

      Transition from state \ (\ left(i - 1, j - 1, 0, 0\right) \) to state \ (\ left(i, j, 0, 0\right) \).

      Transition from state \ (\ left(i - 1, j - 1, 0, 1\right) \) to state \ (\ left(i, j, 1, 0\right) \).

    • Bit \ (i \) selects \ (i + 1 \):

      Transition from state \ (\ left(i - 1, j - 1, 0/1, 0\right) \) to state \ (\ left(i, j, 0, 1\right) \).

      Transition from state \ (\ left(i - 1, j - 1, 0/1, 1\right) \) to state \ (\ left(i, j, 1, 1\right) \).

  • Bit \ (i \) is not perfect:

    Transition from state \ (\ left(i - 1, j, 0/1, 0\right) \) to state \ (\ left(i, j, 0, 0\right) \).

    Transition from state \ (\ left(i - 1, j, 0/1, 1\right) \) to state \ (\ left(i, j, 1, 0\right) \).

  And \ (f (x) = \ left (DP {n, x, 0, 0} + DP {n, x, 1, 1} \ right) \ times \ left (n - x \ right)! \), so we can find \ (g(x) \). The final answer is \ (g(m) \).

  Note that at this time \ (dp_{i,j,0/1,0/1} \) can be reduced to \ (dp_{0 / 1, J, 0 / 1,0 / 1} \).

  Time complexity \ (\ theta \ left (n ^ 2 \ right \).

  code:

  Click to view the code

  // =============================================
  // The horizontal line, the victory, and the carving!
  // Author: Sasebo Shiyu
  // Blog: https://www.cnblogs.com/SasebonoShigure
  // =============================================
  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  using namespace std;
  typedef long long LL;
  const LL Mod = 1e9 + 7;
  const int Maxn = 1e3 + 10;
  int n, m;
  int Count[Maxn];
  LL Answer;
  LL f[Maxn][Maxn][2][2], Fact[Maxn], Inv[Maxn];
  inline LL Qkpow (LL Base, LL x) {
  	LL Pow = 1;
  	while (x ) {
  		if (x & 1 ) {
  			Pow = Pow * Base % Mod;
  		}
  		x >>= 1, Base = Base * Base % Mod;
  	}
  	return Pow;
  }
  inline LL Getinv (const LL Num) {
  	return Qkpow (Num, Mod - 2);
  }
  inline LL Getbinom (const int n, const int m) {
  	return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod;
  }
  signed main () {
  	scanf ("%d %d", &n, &m), Fact[0] = 1;
  	f[1][0][0][0] = f[1][1][0][1] = 1;
  	for (int i = 1; i <= n; ++ i ) {
  		Fact[i] = Fact[i - 1] * i % Mod;
  	}
  	Inv[n] = Getinv (Fact[n]);
  	for (int i = n - 1; ~i; -- i ) {
  		Inv[i] = Inv[i + 1] * (i + 1) % Mod;
  	}
  	for (int i = 2; i <= n; ++ i ) {
  		f[i][0][0][0] = 1;
  		for (int j = 1; j <= i; ++ j ) {
  			f[i][j][0][0] = (f[i - 1][j - 1][0][0] + f[i - 1][j][0][0] + f[i - 1][j][1][0]) % Mod;
  			f[i][j][1][0] = (f[i - 1][j - 1][0][1] + f[i - 1][j][0][1] + f[i - 1][j][1][1]) % Mod;
  			f[i][j][0][1] = (f[i - 1][j - 1][0][0] + f[i - 1][j - 1][1][0]) % Mod;
  			f[i][j][1][1] = (f[i - 1][j - 1][0][1] + f[i - 1][j - 1][1][1]) % Mod;
  		}
  	}
  	for (int i = m, Tag = 1; i <= n; ++ i, Tag = -Tag ) {
  		Answer = (Answer + Tag * Getbinom (i, m) * (f[n][i][0][0] + f[n][i][1][0]) % Mod * Fact[n - i] % Mod + Mod) % Mod;
  	}
  	printf ("%lld\n", Answer);
  	return 0;
  }