[tsinsen_A1278]串珠子

試題描述

銘銘有 \(n\) 個十分漂亮的珠子和若干根顏色不同的繩子?，F在銘銘想用繩子把所有的珠子連接成一個整體。

現在已知所有珠子互不相同，用整數 \(1\) 到 \(n\) 編號。對于第 \(i\) 個珠子和第 \(j\) 個珠子，可以選擇不用繩子連接，或者在 \(c_{i,j}\) 根不同顏色的繩子中選擇一根將它們連接。如果把珠子看作點，把繩子看作邊，將所有珠子連成一個整體即為所有點構成一個連通圖。特別地，珠子不能和自己連接。

銘銘希望知道總共有多少種不同的方案將所有珠子連成一個整體。由于答案可能很大，因此只需輸出答案對 \(1000000007\) 取模的結果。

輸入

標準輸入。輸入第一行包含一個正整數 \(n\)，表示珠子的個數。接下來 \(n\) 行，每行包含 \(n\) 個非負整數，用空格隔開。這 \(n\) 行中，第 \(i\) 行第 \(j\) 個數為 \(c_{i,j}\)。

輸出

標準輸出。輸出一行一個整數，為連接方案數對 \(1000000007\) 取模的結果。

輸入示例

3 0 2 3 2 0 4 3 4 0

輸出示例

50

數據規模及約定

對于 \(100\%\) 的數據，\(n\) 為正整數，所有的 \(c_{i,j}\) 為非負整數且不超過 \(1000000007\)。保證 \(c_{i,j}=c_{j,i}\)。每組數據的 \(n\) 值如下表所示。

編號12345678910

$n$	$8$	$9$	$9$	$10$	$11$	$12$	$13$	$14$	$15$	$16$

題解

一道挺經典的狀壓 dp，這題有一些計數技巧。

狀態很簡單，就是令 \(f(s)\) 表示集合 \(s\) 內所有點處于一個連通分量內的方案數，關鍵是怎么轉移。

為了讓計算的方案不重不漏，我們需要設計一個方案使得每次轉移都是唯一的，不會被重復轉移，同時也能夠讓轉移覆蓋到所有情況。

這題就是找到集合 \(s\) 中的前兩個元素（或者第一個和最后一個元素也行，需要保證每次都選的是特定的兩個元素），令第一個為 \(t_1\)，第二個為 \(t_2\)，然后我們要枚舉第一次拆解（這次拆解后的兩個集合都通過 \(t_1\) 這個點相連，即 \(t_1\) 是 \(s\) 連通分量的割頂），并且由于這個拆解是沒有順序的，所以我們要保證每次拆解都需要將 \(t_1\) 和 \(t_2\) 分開。于是枚舉 \(s\) 的子集 \(s'\)，使得 \(t_2 \in s'\) 且 \(t_1 \in s - s'\)，然后將 \(s\) 分成 \(s'\) 和 \(s - s'\) 兩個集合，最后轉移就是 \(f(s) = f(s') \cdot f(s-s') \cdot \prod_{i \in s'} {c_{t_1, i}}\)。

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std; #define rep(i, s, t) for(int i = (s); i <= (t); i++) #define dwn(i, s, t) for(int i = (s); i >= (t); i--)const int BufferSize = 1 << 16; char buffer[BufferSize], *Head, *Tail; inline char Getchar() {if(Head == Tail) {int l = fread(buffer, 1, BufferSize, stdin);Tail = (Head = buffer) + l;}return *Head++; } int read() {int x = 0, f = 1; char c = Getchar();while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }return x * f; }#define maxn 20 #define maxs 65536 #define MOD 1000000007 #define LL long longint n, c[maxn][maxn], Log[maxs], f[maxs], mul[maxn][maxs];int main() {n = read();rep(i, 0, n - 1) rep(j, 0, n - 1) c[i][j] = read();int all = (1 << n) - 1;Log[1] = 0;rep(i, 2, all + 1) Log[i] = Log[i>>1] + 1;rep(i, 0, n - 1) {mul[i][0] = 1;rep(s, 1, all) mul[i][s] = (LL)mul[i][s&~(s&-s)] * (c[i][Log[s&-s]] + 1) % MOD;}rep(s, 1, all) {int cnt = 0, t1 = -1, t2 = -1;rep(i, 0, n - 1) if(s >> i & 1) {cnt++;if(t1 < 0) t1 = i;else if(t2 < 0) t2 = i;}if(cnt == 1){ f[s] = 1; continue; }for(int ts = (s - 1 & s); ts; ts = (ts - 1 & s)) if((ts >> t2 & 1) && !(ts >> t1 & 1)) {f[s] += (LL)f[ts] * f[s^ts] % MOD * (mul[t1][ts] + MOD - 1) % MOD;if(f[s] >= MOD) f[s] -= MOD;}}printf("%d\n", f[all]);return 0; }

轉載于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/7998910.html

總結

以上是生活随笔為你收集整理的[tsinsen_A1278]串珠子的全部內容，希望文章能夠幫你解決所遇到的問題。

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