精講 組合、容斥

文章目錄

• • 題目：
  • 題意&&題解：：
  • 代碼：

題目傳送

題目：

時(shí)間限制：C/C++ 1秒，其他語(yǔ)言2秒
空間限制：C/C++ 524288K，其他語(yǔ)言1048576K
64bit IO Format: %lld

題目描述

給定一個(gè)完全二分圖，圖的左右兩邊的頂點(diǎn)數(shù)目相同。我們要給圖中的每條邊染成紅色、藍(lán)色、或者綠色，并使得任意兩條紅邊不共享端點(diǎn)、同時(shí)任意兩條藍(lán)邊也不共享端點(diǎn)。
計(jì)算所有滿(mǎn)足條件的染色的方案數(shù)，并對(duì)10⁹+7取模。 (ps：本題數(shù)據(jù)量與實(shí)際比賽中數(shù)據(jù)量相比，少了一些)

輸入描述:

二分圖單邊的頂點(diǎn)數(shù)目n(n ≤ 10^7)

輸出描述:

輸出一個(gè)整數(shù),即所求的答案。

示例1
輸入

2

輸出

35

題意&&題解：：

完全二分圖:是一種特殊的二分圖，可以把圖中的頂點(diǎn)分成兩個(gè)集合，使得第一個(gè)集合中的所有頂點(diǎn)都與第二個(gè)集合中的所有頂點(diǎn)相連。
我們可以把左右各有n個(gè)點(diǎn)的二分圖的題轉(zhuǎn)化成n*n的棋盤(pán)問(wèn)題。（離散上學(xué)過(guò)）
題目：讓染三個(gè)顏色，紅藍(lán)綠，但是綠色并沒(méi)有什么要求，我們可以最后再隨便放。所以我們先考慮紅和藍(lán)。
紅和藍(lán)都是不能共享端點(diǎn)，同步到棋盤(pán)上（行和列分別表示二分圖兩個(gè)集合），也就是棋盤(pán)上行和列只能有一個(gè)紅或藍(lán)

現(xiàn)在的題目就是：
在n*n的棋盤(pán)上，放任意紅和藍(lán)棋子，任一行和列不能有相同顏色的棋子，有多少種放的方法？
F_n表示棋盤(pán)大小為 n * n時(shí)的答案
先只考慮一個(gè)顏色： F_n=種方案(先在n行里選若干行，然后每一行選若干列，行沒(méi)有順序區(qū)分，就是選兩行，選第一行和第三行與選第一行和第二行沒(méi)差，所以選行用組合；而列不一樣，因?yàn)樾辛兄荒芊乓粋€(gè)，我們可以先放在一行上，然后分散到其他行，所以選列的時(shí)候要考慮順序問(wèn)題，要用的是排列而不是組合)
如圖：

比如我們選兩行（C² _n ），然后每行放一個(gè)，我們先考慮都放在一行上，看圖中最上面兩行（黃色和綠色），都是選的第一個(gè)格和第二個(gè)格，但是分散開(kāi)不一樣，（圖中4 * 4的表格）說(shuō)明我們要考慮順序，所以選列是A²_n，將所以情況加起來(lái)就是選一個(gè)顏色的方案

選兩個(gè)顏色：從上面我們能得到一個(gè)顏色是F_n，兩個(gè)就是F_n* F_n，非也，因?yàn)檫@樣會(huì)出現(xiàn)一個(gè)格子放兩個(gè)棋子，我們還要將這種情況刪去。需要容斥。
我們用g_i表示最少有i個(gè)點(diǎn)放了兩個(gè)棋子（顏色不一樣）的方案數(shù)。那么除去i 行和i 列（i個(gè)點(diǎn)所在），我們?cè)谑Ｏ耼-i行與列里就不會(huì)有重復(fù)的，g_i = f ²_n-i 。被除去的 i 行與 i列選法和之前一樣是 Cⁱ_nAⁱ_n ，最后得到容斥公式：

（這一部分好好理解）

C^k_nA^k_n都可以求好，但是Fn提前求會(huì)超時(shí)，說(shuō)明上面的公式不能用，我們要換一個(gè)想法來(lái)求
我們來(lái)考慮F_n能不能遞推出來(lái)，從F_n-1推出F_n
考慮n-1到n的過(guò)程：
一共增加了2n-1個(gè)格子（n²-(n-1)²）,n-1之前的格子都已經(jīng)放好了，我們只需要考慮多出的這些格子該怎么放。
如果只放一個(gè)棋子，就有2n-1個(gè)方案，如果都不放，一個(gè)方案，一共是2n種方案，也就是2nF_n-1，（F_n-1是之前n-1行列已經(jīng)放好的方案數(shù)）
但是有限制條件，每一行不能有相同顏色，每放一個(gè)棋子，意味著這一行這一列都不能放了，就會(huì)出現(xiàn)n-1種重復(fù)情況（因?yàn)槭菑膎-1的擴(kuò)展來(lái)的），我們之前n-1行列的棋子都平移靠邊，因?yàn)橹岸际遣煌型?#xff0c;所以靠邊后，正好占了一行一列，也就是我們?cè)谛略霾糠挚梢苑诺钠遄?#xff0c;實(shí)際上是F_n-2而非F_n-1（這里可以看看圖），那一共（n-1）F_n-2次重復(fù)情況，可以選n-1行，而且每一列也可以進(jìn)行相同操作,總的方案數(shù)就是2×(n?1) ² ?F(n?2)
借鑒鄧?yán)蠋煹膱D：

我們還要考慮放兩個(gè)的情況;
即最后一行和列分別放一個(gè)，這樣不重復(fù)嘛
方案就是：（n-1）²F(n-2)

總結(jié)：得到公式
F[n]=2nF[n-1]-(n-1)²F[n-2]
（我真的是把我所能理解都寫(xiě)出來(lái)了 ）

代碼：

#include<cstdio> #include<iostream> #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 10000004; const int mod = 1e9 + 7;int g[N],s[N],F[N]; ll C(int n,int m) {return 1ll * g[n] * s[m] % mod * s[n - m] % mod; } ll A(int n,int m) {return 1ll * g[n] * s[n - m] % mod; } int main() {cin>>n;g[0] = 1;for(int i = 1;i <= n;++i)g[i] = 1ll * g[i - 1] * i % mod;ll ans1 = 1;for(;y;y >>= 1,x = x * x % mod){if(y & 1) ans1 = ans1 * x % mod;}s[n] = ans1;for(int i = n - 1;i >= 0;--i)s[i] = 1ll * s[i + 1] * (i + 1) % mod;F[0] = 1;F[1] = 2;for(int i = 2;i <= n;++i)F[i] = (2ll * i * F[i - 1] - 1ll * F[i - 2] * (i - 1) % mod * (i - 1) % mod) % mod;ll ans = 0;ll k ;for(int i = 0;i <= n;++i) {k=1;if(i & 1) k = -1;ans += k * C(n,i) * A(n,i) % mod * F[n - i] % mod * F[n - i] % mod;ans %= mod;}printf("%lld\n",(ans + mod) % mod);return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客网 【每日一题】4月10日 二分图染色(弱化版)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。