文章目錄

• description
• solution
• code

description

有$T$組測試數(shù)據(jù)

對于兩個長度為$K$的數(shù)列$\{a\}$和$\{b\}$，滿足${\sum }_{i=1}^K{a}_i=N,{\sum }_{i=1}^K{b}_i=M$

對于這兩個數(shù)列，定義權(quán)值為$P={\prod }_{i=1}^K\min (a_i,b_i)$

求所有可能的數(shù)列的權(quán)值之和${\sum }_{\{a\},\{b\}}P$

答案對$998244353$取模

$K\le \min (N,M)N,M\le 5e5T\le 100$

solution

雖然代碼非常短，但是要理解簡直要命

我們可以構(gòu)造一個二維數(shù)組$c[2][K]$，要求$c[0][i]=c[1][i]$，第i位不能為0

設(shè)計的初衷是讓$c[0][K]$為構(gòu)造$\{a\}$，$c[1][K]$為構(gòu)造$\{b\}$服務(wù)

再構(gòu)造兩個一維數(shù)組$A[K],B[K]$，第i位可以為0

通過構(gòu)造出來的這些數(shù)組生成最后的$\{a\},\{b\}$

• $a[i]=c[0][i]+A[i]$
• $b[i]=c[1][i]+B[i]$

定義${\sum }_{i=1}^{K}c[0][i]={\sum }_{i=1}^{K}c[1][i]=S$

則對于$\{a\}$序列而言，剩下的$N?S$就需要由$A$數(shù)組來彌補(bǔ)；$\{b\}$同理

考慮有多少個$A/B$數(shù)組滿足其求和恰好彌補(bǔ)了空缺$N?S/M?S$

顯然這可以通過組合數(shù)算出

• $A:C(N?S+K?1,K?1)$
• $B:C(M?S+K?1,K?1)$

以$A$數(shù)組的計算方式為例，$B$同理

相當(dāng)于把剩下的$N?S$分成恰好$K$個盒子，隔板法，插入$K?1$個板子

但是$A$的條件可以為$0$，意味著盒子可以為空，但這是隔板法不能求得的

可以通過給每個盒子分配$1$的占位相當(dāng)于一個盒子，等價于將限制變成至少為$1$

考慮$C(N?S+K?1,K?1)?C(M?S+K?1,K?1)$

發(fā)現(xiàn)這兩個組合數(shù)相乘有非常實(shí)際的意義

這求出的恰好是將所有滿足${?}_{1\le i\le K}c[0][i]\le a[i]$的$\{a\}$和${?}_{1\le i\le K}c[0][i]\le b[i]\{b\}$的組合都計算了恰好一次

---

接著我們考慮對于一組特定的$c$數(shù)組和特定的$A,B$數(shù)組（也就是一組特定的$\{a\},\{b\}$）的貢獻(xiàn)

${\prod }_{i=1}^K\min (a_i,b_i)$ 這是題目定義的貢獻(xiàn)

思考一下，這樣一組特定的$\{a\},\{b\}$，會被多少個$c$計算到？

• 顯然是${\prod }_{i=1}^K\min (a_i,b_i)$

  每一位$i$都滿足$c[0][i]=c[1][i]\le \min (a_i,b_i)$就行，因為$c$要求不能為$0$，而$A,B$要求可以為$0$

  將每一位$c[i]$的可取值個數(shù)相乘，即是能利用$A,B$修補(bǔ)成$\{a\},\{b\}$的所有$c$的組合

于是乎，發(fā)現(xiàn)非常巧妙地將答案的乘積和轉(zhuǎn)化成了計數(shù)個數(shù)貢獻(xiàn)

再轉(zhuǎn)個彎，我們直接計算每個特定的$c$會對多少個$\{a\},\{b\}$提供$1$的計數(shù)貢獻(xiàn)，求和就等價于原問題的總貢獻(xiàn)

然而，又發(fā)現(xiàn)了一個非常巧妙的性質(zhì)，和(S)相同的$c$產(chǎn)生的計數(shù)貢獻(xiàn)是一樣的（但不是貢獻(xiàn)的$\{a\},\{b\}$完全相同的意思）

• 要證明這個性質(zhì)，就需要再轉(zhuǎn)個彎，用到最開始的組合數(shù)推導(dǎo)

  剩下的$N?S,M?S$都需要$A,B$的補(bǔ)給

  $A,B$怎么補(bǔ)給，最后生成的$\{a\},\{b\}$會因此而固定

  是一對一的關(guān)系

這個計數(shù)貢獻(xiàn)自然是$C_{S?1,K?1}$

• 插板法

  $c$的和為$S$，要求分成$K$個盒子，盒子不能為空

  相當(dāng)于有$S?1$個空位需要插入$K?1$個板

最后就成功不用生成函數(shù)解決這道題了！！！

現(xiàn)在總結(jié)，就只有一句話，最開始的$c,A,B$構(gòu)造簡直就是神來之筆

后面所有的推導(dǎo)全都是建立在最開始的規(guī)則設(shè)定基礎(chǔ)上

真的妙極了！！

code

#include <cstdio> #include <iostream> using namespace std; #define int long long #define mod 998244353 #define maxn 1000005 int fac[maxn], inv[maxn];int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }void init( int n ) {fac[0] = inv[0] = 1;for( int i = 1;i <= n;i ++ )fac[i] = fac[i - 1] * i % mod;inv[n] = qkpow( fac[n], mod - 2 );for( int i = n - 1;i;i -- )inv[i] = inv[i + 1] * ( i + 1 ) % mod; }int C( int n, int m ) {return fac[n] * inv[m] % mod * inv[n - m] % mod; }signed main() {init( 1e6 );int n, m, k, T;scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld %lld", &n, &m, &k );int ans = 0;for( int i = k;i <= min( n, m );i ++ )ans = ( ans + C( i - 1, k - 1 ) * C( n - i + k - 1, k - 1 ) % mod * C( m - i + k - 1, k - 1 ) ) % mod;printf( "%lld\n", ans );}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2020年牛客多校第五场C题-easy(纯组合计数不要生成函数的做法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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