2025.9.28 組合計數

這篇博客只會寫一些題解，基礎內容和另外一些題，見：

P4492 [HAOI2018] 蘋果樹

Hint：相當于求所有形態二叉樹的路徑和，考慮一條邊 \((u,fa_u)\) 的貢獻.

記子樹 \(u\) 的大小為 \(sz_u\)，把所有路徑和拆成每條邊會貢獻到多少條路徑里面，發現這就是 \(sz_u\times(n-sz_u)\). 我們考慮從小到大枚舉每個標號，并且枚舉子樹大直接計算答案.

由于二叉樹是一個節點一個節點生成的，相當于有標號. 考慮標號的影響，填到標號 \(i\) 時，前面標號任意，貢獻為 \(i!\)；子樹中標號貢獻 \(sz_i!\). 考慮子樹生成的方案數，剩下的點選 \(sz_i-1\) 個，其他點全部填到子樹外面，方案數為 \({(n-sz_i-1)!\over (i-2)!}\).

最終答案的式子就是：

\[\sum_{i=2}^n\sum_{x=1}^{n-i+1}{x(n-x)\cdot i!{n-i\choose x-1}\cdot x!\cdot{(n-x-1)!\over (i-2)!}} \]

考慮二叉樹的生成方案有 \(n!\) 種，因為加入節點 \(i\) 時有 \(i\) 種位置，加入之后總位置又會增加 \(1\). 所以最終答案就是上面那個式子.

P1450 [HAOI2008] 硬幣購物

Hint：背包預處理，枚舉子集暴力容斥.

硬幣數量的限制不好處理，容斥成不考慮限制的方案數減去所有不合法的方案數. 總方案數可以直接完全背包預處理，考慮欽定硬幣種類的一個子集超出了限制，子集預先選 \(d_i+1\) 個硬幣，方案數是預處理好的. 直接容斥即可.

P10681 [COTS 2024] 奇偶矩陣 Tablica

Hint：考慮一個題意轉化：\(a\) 種顏色 \(1\) 個球，另外 \(b\) 種顏色 \(2\) 個球，\(c\) 個有序集合放一個球，\(d\) 個有序集合放兩個球且不能有相同顏色的方案數.

上述轉化相當于把 \(a\) 行的 \(1\) 和 \(b\) 行的 \(2\) 分配給 \(c,d\) 列. 首先 \(a,b,c,d\) 滿足三個等式.

\[\begin{cases} a+b=n\\ c+d=m\\ a+2b=c+2d \end{cases} \]

這是易于枚舉的，下面考慮確定的 \(a,b,c,d\) 如何統計方案.

把 \(a+2b\) 個球排列，按順序分配給 \(c + d\) 個集合，考慮容斥掉非法的情況：

\(\{x,y\}\) 和 \(\{y,x\}\) 被重復統計.
出現 \(\{x,x\}\) 的集合.

前者的處理可以在最后答案除以 \(2^d\)，后者考慮容斥，欽定 \(t\) 個集合放相同元素，于是剩下的 \(a+2(b-t)\) 個球排列，最終式子為：

\[\sum_{a+b=n,c+d=m,a+2b=c+2d}{n\choose a}{m\choose b}\sum_{t=0}^{\min(b,d)}{(-1)^t{b\choose t}{d\choose t}t!{(a+2b-2t)!\over2^{b-t}}\over2^d} \]

P11030 『DABOI Round 1』Blessings Repeated

Hint：預處理出 \(T\) 每個區間被 \(S\) 包含的子序列數量，爆搜 \(T\) 的分拆統計答案.

\(k\) 很大，顯然不能直接暴力做. 考慮最終的方案一定形如從 \(k\) 串中選擇若干個，依次匹配 \(T\) 中的一段. 先預處理 \(f_{i,l,r}\) 表示前綴 \(i\) 中 \(T[l\cdots r]\) 的子序列方案數，有轉移：

\[\begin{cases} f_{i,l,r}\leftarrow f_{i-1,l,r}&(s_i\neq t_r)\\ f_{i,l,r}\leftarrow f_{i-1,l,r}+1&(s_i=t_r\wedge l=r)\\ f_{i,l,r}\leftarrow f_{i-1,l,r}+f_{i-1,l,r-1}&(\text{otherwise.}) \end{cases} \]

然后直接爆搜劃分統計答案即可.

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5e3 + 10, maxm = 1e1 + 5, mo = 998244353;
const int inv[11] = {0, 1, 499122177, 166374059, 291154603, 856826403, 641926577, 376916469, 421456191, 712324701, 370705776};
ll n, m, k; char s[maxn], t[maxm];
ll f[maxn][maxm][maxm], ans;

inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : (x + y < 0 ? x + y + mo : x + y);}
inline void upd(ll &x, const int &y) {return x = add(x, y), void(0);}

inline ll C(int x) {
	ll res = 1;
	for(int i = 0; i < x; i++) (res *= (k - i) % mo) %= mo;
	return res * inv[x] % mo;
}
void dfs(int p, int cnt, ll res) {
	if(p > m) return upd(ans, res * C(cnt) % mo);
	for(int i = p; i <= m; i++) dfs(i + 1, cnt + 1, res * f[n][p][i] % mo);
}

int main() {
	ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> k >> (s + 1) >> (t + 1); n = strlen(s + 1), m = strlen(t + 1);
	for(int i = 1; i <= n; i++) for(int l = 1; l <= m; l++) for(int r = l; r <= m; r++) {
		f[i][l][r] = f[i - 1][l][r];
		if(s[i] == t[r]) upd(f[i][l][r], (l == r ? 1 : f[i - 1][l][r - 1]));
	} dfs(1, 0, 1);

	cout << ans;
	
	return 0;
}

P9129 [USACO23FEB] Piling Papers G

Hint：考慮數位 DP 預處理出所有區間的答案.

首先差分，轉換成求在 \(1\sim x\) 范圍的答案. 考慮一個恰當的 DP 方程是 \(f_{l,r,i,j,0/1/2}\) 表示區間 \([l,r]\) 拼出的數字相比于 \(x\) 從低到高 \(i\) 到 \(j\) 位小于/大于/等于的方案數. 轉移分討在加在左邊還是右邊，以及與 \(x\) 這一位的大小關系即可.

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 3e2 + 10, mo = 1e9 + 7;
int n, q, a[maxn], b[20], tot; ll A, B;
int ans[maxn][maxn], f[20][20][3];

inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : (x + y < 0 ? x + y + mo : x + y);}
inline void upd(int &x, const int &y) {return x = add(x, y), void(0);}

inline int cmp(const int &x, const int &y) {return x == y ? 2 : x > y;}
void calc(ll V, int op) {
    tot = 0;
    while(V) {b[++tot] = V % 10, V /= 10;} reverse(b + 1, b + tot + 1);

    for(int l = 1; l <= n; l++) {
        memset(f, 0, sizeof f);
        for(int r = l; r <= n; r++) {
            for(int i = 1; i <= tot; i++) for(int j = tot; j > i; j--) for(int k = 0; k < 3; k++) {
                if(a[r] == b[i]) upd(f[i][j][k], f[i + 1][j][k]);
                else upd(f[i][j][cmp(a[r], b[i])], f[i + 1][j][k]);
                if(k != 2) upd(f[i][j][k], f[i][j - 1][k]);
                else upd(f[i][j][cmp(a[r], b[j])], f[i][j - 1][k]);
            }
            for(int i = 1; i <= tot; i++) upd(f[i][i][cmp(a[r], b[i])], 2);
            for(int i = 1; i <= tot; i++) {
                upd(ans[l][r], op * f[i][tot][0]);
                upd(ans[l][r], op * f[i][tot][2]);
                if(i > 1) upd(ans[l][r], op * f[i][tot][1]);
            }
        }
    } return;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> A >> B;
    for(int i = 1; i <= n; i++) cin >> a[i];

    calc(A - 1, -1), calc(B, 1);

    cin >> q;
    while(q--) {
        int l, r; cin >> l >> r;
        cout << ans[l][r] << "\n";
    }

    return 0;
}

P4448 [AHOI2018初中組] 球球的排列

Hint：觀察到乘積為平方具有傳遞性，于是維護顏色，DP 狀態區分顏色來進行轉移.

我們把每一個點的顏色設為序列里面第一個乘積為平方的位置，為了方便 DP，把所有數先按顏色排序.

考慮填一個數的情況，我們可以往同色對插入一個異色來將其變為合法的，所以要討論顏色之間的關系. 設 \(f_{i,j,k}\) 表示填完前 \(i\) 個數之后有 \(j\) 對與 \(i\) 顏色不同的相鄰對，有 \(k\) 對與 \(i\) 同色的相鄰對，記錄同色的個數 \(cnt\). 轉移分類討論：

\(i\) 與 \(i-1\) 異色，\(i\) 插入異色對.
\(i\) 與 \(i-1\) 異色，\(i\) 插入同色對.
\(i\) 與 \(i-1\) 同色，\(i\) 插入同色球旁邊.
\(i\) 與 \(i-1\) 同色，\(i\) 插入同色對.
\(i\) 與 \(i-1\) 同色，\(i\) 插入異色對.

分別有轉移：

\[f_{i,j,0}\leftarrow f_{i-1,j',j-j'}\times(i-j) \]

\[f_{i,j,0}\leftarrow f_{i-1,j',j-j'+1}\times(j+1) \]

\[f_{i,j,k}\leftarrow f_{i-1,j,k-1}\times(cnt\times2-k+1) \]

\[f_{i,j,k}\leftarrow f_{i-1,j+1,k}\times(j+1) \]

\[f_{i,j,k}\leftarrow f_{i-1,j,k}\times(i-cnt\times2 + k-j) \]

注意邊界；滾動數組.

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 3e2 + 10, mo = 1e9 + 7;
int n, a[maxn], b[maxn];
int f[2][maxn][maxn];

inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : x + y < 0 ? x + y + mo : x + y;}
inline void upd(int &x, const int &y) {return x = add(x, y), void(0);}
inline ll sqr(const ll &x) {return x * x;}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i]; b[i] = i;
        for(int j = 1; j < i; j++) if(sqr(sqrt(1ll * a[i] * a[j])) == 1ll * a[i] * a[j]) {b[i] = j; break;}
    } sort(b + 1, b + n + 1);
    f[0][0][0] = 1;
    for(int i = 1, cnt = 0; i <= n; i++) {
        int o = i & 1;
        memset(f[o], 0, sizeof f[o]);
        if(b[i] != b[i - 1]) {
            cnt = 0;
            for(int j = 0; j < i; j++) for(int j0 = 0; j0 <= j + 1; ++j0) {
                if(j0 <= j) upd(f[o][j][0], 1ll * f[o ^ 1][j0][j - j0] * (i - j) % mo);
                upd(f[o][j][0], 1ll * f[o ^ 1][j0][j - j0 + 1] * (j + 1) % mo);
            }
        }
        else {
            for(int j = 0; j < i; j++) for(int k = 0; k <= cnt; k++){
                if(k > 0) upd(f[o][j][k], 1ll * f[o ^ 1][j][k - 1] * (cnt * 2 - k + 1) % mo);
                upd(f[o][j][k], 1ll * f[o ^ 1][j + 1][k] * (j + 1) % mo);
                upd(f[o][j][k], 1ll * f[o ^ 1][j][k] * (i - cnt * 2 + k - j) % mo);
            }
        } cnt++;
    } cout << f[n & 1][0][0];

    return 0;
}

posted @ 2025-10-01 19:38 Ydoc770 閱讀(20) 評論(1) 收藏舉報

刷新頁面返回頂部

公告