組合計數我最愛

• Max-Min Sums
• • description
  • solution
  • code
• Binomial Coefficient is Fun
• • description
  • solution
  • code
• Strivore
• • description
  • solution
  • code
• Bubble Sort
• • description
  • solution
  • code
• [HAOI2016]放棋子
• • description
  • solution
  • code
• EntropyIncreaser 與 Minecraft
• • description
  • solution
  • code
• D - Iroha and a Grid
• • description
  • solution
  • code

Max-Min Sums

description

solution

加法對于$\max /\min$有分配率，所以單獨考慮每個$i$做最大值/最小值的貢獻，加起來即可

把$a$排序后，前面選$k?1$個自己做最大值，后面選$k?1$個自己做最小值

code

#include <cstdio> #include <algorithm> using namespace std; #define mod 1000000007 #define int long long #define maxn 100005 int n, k; int A[maxn], sum[maxn], 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; }int C( int n, int m ) {if( n < m ) return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod; }signed main() {scanf( "%lld %lld", &n, &k );inv[0] = fac[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;for( int i = 1;i <= n;i ++ )scanf( "%lld", &A[i] );sort( A + 1, A + n + 1 );int ans = 0;for( int i = 1;i <= n;i ++ )ans = ( ans + C( i - 1, k - 1 ) * A[i] - C( n - i, k - 1 ) * A[i] ) % mod;printf( "%lld\n", ( ans + mod ) % mod );return 0; }

Binomial Coefficient is Fun

description

solution

要乘積產生貢獻，必須滿足$B_i\ge A_i$，${\sum }_i{B}_i\le m$，看成$m$個空位

把至少要求的$A_i$看成第$i$根小棒，不同$i$之間加一條分割線分開，$A_n$的分割線則劃分了${\sum }_i{B}_i$的范圍

總共是$n+m$個空位（新增了$n$條分割線空位），從中放${\sum }_i{A}_i+n$根小棒和分割線

小棒和分割線是沒有區別的，用組合數求

前$A_1$根小棒劃分范圍表示$B_1$，以第$A_1+1$根小棒（分割線）劃分不同的$B$

第$A_1+2$到$A_1+B_1+1$根小棒劃分范圍表示$B_2$，以此類推

就與問題的所求式子方案對應

code

#include <cstdio> #define int long long #define mod 1000000007 int n, m, sum;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; }signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1, x;i <= n;i ++ )scanf( "%lld", &x ), sum += x;int ans = 1;for( int i = m - sum + 1;i <= n + m;i ++ )ans = ans * i % mod;for( int i = 1;i <= sum + n;i ++ )ans = ans * qkpow( i, mod - 2 ) % mod;printf( "%lld\n", ans );return 0; }

Strivore

description

solution

轉化為求$n+|s|$的字符串，使得$s$是其一個（可以不相鄰的）子序列

非常惡心的就是如果插入的字符與相鄰字符相同，那么插左邊插右邊本質是沒有區別的

只有個數的改變，但是如果單純用組合數來算，顯然會算成多種方案

e.g. 要插o在oo中，插左/插右/插中間，最后結果都是ooo，理應算成一種

所以強制的分類，左右邊，在右邊的數就可以隨便選，在左邊的數，就強制與即將相鄰字符不同

枚舉字符串$s$最后一位的位置（相當于枚舉在右邊的數的個數）

在其右邊的隨便選，左邊的去除掉禁止的字符

$$\sum _{i=0}^{n}26^i\times 25^{n?i}{C}_{n?i+|s|?1}^{n?i}$$

$|s|?1$就是減去字符串最后一位位置，因為右邊個數確定，伴隨著最后一個位置確定

有$n?i$個位置還可以隨便選，剩下的位置就必須按照$s$的長相依次填充

code

#include <cstdio> #include <cstring> #define maxn 2000005 #define int long long #define mod 1000000007 int fac[maxn], inv[maxn]; char s[maxn]; int n, m;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() {scanf( "%lld %s", &n, s + 1 );m = strlen( s + 1 );init( n + m );int ans = 0;for( int i = 0;i <= n;i ++ )ans = ( ans + qkpow( 26, i ) * qkpow( 25, n - i ) % mod * C( n - i + m - 1, n - i ) % mod ) % mod;printf( "%lld\n", ans );return 0; }

Bubble Sort

description

solution

定義函數$f(x):x$元素左邊且比$x$大的元素個數

• ${?}_{x}f(x)=0$表示有序狀態
• $f(x)\le n?x$
• 每一輪的冒泡排序，若$f(x)=0$，則$f(x)??$

顯然$\max \{f(x)\}=k$才恰好是$k$輪的冒泡排序

比起求恰好$k$輪的冒泡排序，不超過$k$輪的冒泡排序$g(k)$更好求

${?}_{x}n?x\le k?n?k\le x$，滿足此條件的$x$可以隨便放

在$n$個位置中放置$n?k$個數后，剩下數的放置方案數$k!$

對于前$n?k$個放置的數

$f(1)\le k?1$有$k+1$個位置可以放（前$k+1$個），$1$對$f(2)$不會有影響，所以$2$同樣有$k+1$個位置可放$...$

最終結果為$g(k)?g(k?1)=k!((k+1{)}^{n?k}?k^{n?k})$

code

#include <cstdio> #define int long long #define mod 20100713 #define maxn 1000005 int fac[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; } signed main() {int T, n, k;scanf( "%lld", &T );fac[0] = 1;for( int i = 1;i <= 1e6;i ++ )fac[i] = fac[i - 1] * i % mod;while( T -- ) {scanf( "%lld %lld", &n, &k );printf( "%lld\n", ( qkpow( k + 1, n - k ) - qkpow( k, n - k ) + mod ) % mod * fac[k] % mod );}return 0; }

[HAOI2016]放棋子

description

solution

每行每列都只有一個障礙，除去這些障礙，保證每行每列恰好只放了一個棋子的方案數

本質其實就是錯排數，障礙就相當于$i$自身（在方案中不能與$i$下標對應)

知道這個后就剩下大整數操作了

沒有模數真是難，有了模數還是難

code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; struct Int {int g[5000], len;Int() {memset( g, 0, sizeof( g ) );len = 0;}Int( int x ) {memset( g, 0, sizeof( g ) );len = 0;if( ! x ) len = 1;else while( x )g[len ++] = x % 10, x /= 10;}void clean() {while( len > 1 && ! g[len - 1] ) len --;}Int operator + ( Int t ) {static Int ans;ans.len = 0; int r = 0;for( int i = 0;i < max( len, t.len );i ++ ) {int x = r;if( i < len ) x += g[i];if( i < t.len ) x += t.g[i];ans.g[ans.len ++] = x % 10;r = x / 10;}ans.g[ans.len ++] = r;ans.clean();return ans;}Int operator * ( Int t ) {Int ans;ans.len = t.len + len;for( int i = 0;i < len;i ++ )for( int j = 0;j < t.len;j ++ )ans.g[i + j] += g[i] * t.g[j];for( int i = 0;i < ans.len;i ++ )ans.g[i + 1] += ans.g[i] / 10, ans.g[i] %= 10;ans.len ++;ans.clean();return ans;}void print() {for( int i = len - 1;~ i;i -- )printf( "%d", g[i] );} }D[205]; int main() {int n;scanf( "%d", &n );D[1] = 0, D[2] = 1;for( int i = 3;i <= n;i ++ )D[i] = ( D[i - 1] + D[i - 2] ) * ( i - 1 );D[n].print();return 0; }

EntropyIncreaser 與 Minecraft

description

solution

${\sum }_{i=1}^n{x}_i\le p$的形式很難不聯想到Binomial Coefficient is Fun一題的形式

枚舉有多少個$x_i=0$，剩下$k$個$|x_i|>0$，那么方案數首先有$2^k$

設${?}_{i,x_i\ge 0}{y}_i=x_i+1?{\sum }_{i=1}^k{y}_i\le p?{\sum }_{i=1}^k{x}_i\le p?k$

對于${\sum }_{i=1}^k{x}_i=p$的方案數利用$n?1$個檔板的擋板法求解$C_{p+n?1}^{n?1}$

枚舉$p$，答案為${\sum }_{k=0}^n{C}_n^k{2}^k{\sum }_{i=0}^p{C}_{i?k+k?1}^{k?1}?{\sum }_{k=0}^n{C}_n^k{2}^k{\sum }_{i=0}^{p?1}{C}_i^{k?1}$

${\sum }_{i=0}^n{C}_i^m=C_{n+1}^{m+1}?ans={\sum }_{k=0}^n{C}_n^k{2}^k{C}_p^k$

code

#include <cstdio> #define mod 1000000007 #define int long long #define maxn 1000005 int n, p; 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() {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 ) {if( n < m ) return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod; }signed main() {scanf( "%lld %lld", &n, &p );init();int ans = 0, mi = 1, MS = 1;for( int i = 0;i <= n;i ++, mi = ( mi << 1 ) % mod ) {ans = ( ans + C( n, i ) * mi % mod * MS % mod ) % mod;MS = MS * ( p - i ) % mod * qkpow( i + 1, mod - 2 ) % mod;}printf( "%lld\n", ans ); return 0; }

D - Iroha and a Grid

description

solution

從起點到某個點$(i,j)$的方案數：一共走$i?1+j?1$步，從中選$i?1$步往下走，$C_{i+j?2}^{i?1}$

對于本題，有一部分是不能走的，解決方案有兩種（本質一樣，出發角度不同）

• solution1

  總方案?從起點到被禁止區間上一行的，再強制向下走一步，最后被禁止格子到終點的方案

  必須強制向下走一步，如若不然

  則第一個紅格子不合法的方案和第二個紅格子的不合法方案都會包含既經過紅格子1又經過紅格子2的方案

• solution2

  直接計算合法方案數，同樣到被禁止上一行的時候，強制向下走一步

code

#include <cstdio> #define maxn 200005 #define int long long #define mod 1000000007 int n, m, A, B; 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() {fac[0] = inv[0] = 1;for( int i = 1;i < maxn;i ++ )fac[i] = fac[i - 1] * i % mod;inv[maxn - 1] = qkpow( fac[maxn - 1], mod - 2 );for( int i = maxn - 2;i;i -- )inv[i] = inv[i + 1] * ( i + 1 ) % mod; }int C( int n, int m ) {if( n < m ) return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod; }signed main() {init();scanf( "%lld %lld %lld %lld", &n, &m, &A, &B );int ans = 0;for( int i = B + 1;i <= m;i ++ )ans = ( ans + C( n - A + i - 2, i - 1 ) * C( m - i + A - 1, m - i ) % mod ) % mod;printf( "%lld\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的数论三之组合数学Ⅰ-Max-Min Sums,Binomial Coefficient is Fun,Strivore,Bubble Sort,放棋子,LOJ6671,Iroha and a Grid的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。