# 題目: 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