# 題目: UVa 10912 - Simple Minded Hashing

# 題目說明

題目定義一個hashing函數，它是由小寫英文字母的嚴格遞增字串組成，函數值為英文字母的編號數之合
求長度為L，函數值為S時的可能組數

---

INPUT:
每筆測資輸入兩個整數L、S，前者代表字串長度，後者代表函數值

---

OUTPUT:
輸出當字串長度為L，函數值為S時的組數

# 解題方法

題目的範圍過於浮誇
由於限制小寫英文字母，所以a ~ z有26個，而函數值為1 + 2 + ... + 25 + 26 = 351

設一個dp[i][j][k]
i代表選到哪一個字母
j為L，代表字串長度
k為S，代表函數值

字母i可選也可不選，所以dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - i]
(前者不選i，後者選i)

同樣是事先全部建完表後再輸入資料
最後輸出答案dp[26][L][S]

# 參考程式碼

#include <iostream>
#include <memory.h>

using namespace std;

int dp[27][27][352];

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

	int L, S, cases = 0;
	memset(dp, 0, sizeof(dp));
	dp[0][0][0] = 1;

	for (int i = 1; i <= 26; ++i) for (int j = 0; j <= i; ++j) for (int k = 0; k <= 351; ++k)
	{
		dp[i][j][k] = dp[i - 1][j][k];
		if (j && k >= i) dp[i][j][k] += dp[i - 1][j - 1][k - i];
	}

	while (cin >> L >> S, L && S) cout << "Case " << ++cases << ": " << ((L <= 26 && S <= 351) ? dp[26][L][S] : 0) << "\n";

	return 0;
}

# 參考資料

https://blog.csdn.net/mobius_strip/article/details/76640723
https://www.cnblogs.com/staginner/archive/2011/12/17/2291308.html