UVa10721 Bar Codes

題目連結

---

• ❗️ 題意
  bar codes是由黑色與白色的線組合而成，給定n, k, m，分別代表共有n條線，k個bar(分為黑色區域與白色區域，且必定黑白相間，一開始為黑色區域)，每個bar最多由m條線組成，請求給定條件下的所有可能數量。

---

• ✔️ 題解
  再開始題解前，我可以先來思考一個問題
• 舉個例子：假設我們有無限個1元、2元、3元的硬幣，共有幾種方法可以組合出5元?
  • Ans:5(11111, 1112, 113, 122, 23)
• 但其實我們可以透過轉換這個問題為求可能的方法數，變成$(1+x+x^2+x^3+x^4+x^5+..)(1+x^2+x^4+..)(1+x^3+x^6+..)=a_0+a_1x+a_2x^2+…$的解中$x^5$的係數。且由於三個括號中只要x的次方大於5就不會影響到$x^5$的答案，因此我們可以省略成$(1+x+x^2+x^3+x^4+x^5)(1+x^2+x^4)(1+x^3)=a_0+a_1x+a_2x^2+…$，而這個多項式$x^5$的係數為5，也與我們的答案是一樣的。(更多詳細內容可以參考這裡)
• 生成函數到底與這題有什麼關係呢？其實我們可以想像區間其實就是上面例子中的無限個1元，而最高次其實就是m，並且由於我們的區間至少要有一個，所以並沒有常數項。因此此題就變成了：
  $(x+x^2+x^3+..+x^m)^k = a_0x^k+a_1x^{k+1}+a_2x^{k+2}+..$在$x^n$的係數為何?我們還可以將x項提出來，變成$x^k(1+x+x^2+..+x^{m - 1})^k = x^k(a_0+a_1x+a_2x^2+…)$，並左右同除以$x^k$，最後就得到了$(1+x+x^2+..+x^{m - 1})^k = (a_0+a_1x+a_2x^2+…)$，而我們就變成求$x^{n-k}$的係數了。

---

• 💻 程式碼

  #include <bits/stdc++.h>
  using namespace std;
  using LL = long long;
  
  vector<LL> mul(vector<LL> v, vector<LL> base){
  	vector<LL> ans((int)v.size() + (int)base.size() - 1, 0);
  	for(int i = 0; i < (int)v.size(); i++){
  		for(int j = 0; j < (int)base.size(); j++){
  			ans[i + j] += v[i] * base[j];
  		}
  	}
  	return ans;
  }
  int main(){
  	int n, k, m;
  	while(cin >> n >> k >> m){
  		if(k * m < n || n < k){
  			cout << "0\n";
  			continue;
  		}
  		vector<LL>v(m, 1);
  		vector<LL>base(m, 1);
  		for(int i = 0; i < k - 1; i++){
  			v = mul(v, base);
  		}
  		cout << v[n - k] << '\n';
  	}
  	return 0;
  }

  當bar的最長線條數乘以bar的數量小於線條的數量或者線條的數量小於bar的數量都是0

---

• 🧠 心得
  這題大部分的做法都是利用DP的方式來做，連老師介紹這題時也是利用DP。但有一位非常厲害的同學給了給了利用生成函數的想法(在此請收下我的膝蓋🧎‍♂️)，而我也應證了此想法是正確的。

---