問題描述
易老師購買了一盒餅干，盒子中一共有k塊餅干，但是數(shù)字k有些數(shù)位變得模糊了郎嫁，看不清楚數(shù)字具體是多少了修己。易老師需要你幫忙把這k塊餅干平分給n個小朋友，易老師保證這盒餅干能平分給n個小朋友≤酱現(xiàn)在你需要計算出k有多少種可能的數(shù)值
輸入描述
輸入包括兩行：
第一行為盒子上的數(shù)值k，模糊的數(shù)位用X表示，長度小于18(可能有多個模糊的數(shù)位)
第二行為小朋友的人數(shù)n
輸出描述
輸出k可能的數(shù)值種數(shù)寄狼，保證至少為1
輸入例子
9999999999999X
3
輸出例子
4
分析
首先考慮dfs，但是狀態(tài)空間太大（10^18），沒法窮舉泊愧。于是考慮用動態(tài)規(guī)劃伊磺。
1. 狀態(tài)表
dp[i][j]，i={0, 1}删咱，狀態(tài)行屑埋；j為余數(shù)。dp[i][j]表示當(dāng)前所有情況下模n余j的數(shù)量痰滋。
2. 狀態(tài)轉(zhuǎn)移方程
dp[i][(j * 10 + s[p+1]) % n] += dp[!i][j]摘能，如果我們把前p位當(dāng)成一個整體s[0:p]，而且知道了dp[!i][0,n]的值敲街，那么對于前p+1位而言团搞，dp[!i][j]的值會貢獻(xiàn)到dp[i][(j * 10 + s[p+1]) % n]上。如果s[i+1]的值是X多艇，那么我們只要將s[i+1]遍歷10次逻恐。
3. 結(jié)果項
dp[i][0]
note
狀態(tài)轉(zhuǎn)移方程其實不是很懂，據(jù)說是根據(jù)c=a+b<-->c%n=(a%n + b%n)%n推出來的峻黍，但是我并不能看出來= =
代碼
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int MaxN = 100000;
int main()
{
char str[19];
scanf("%s", str);
string k(str);
int n;
scanf("%d", &n);
vector<vector<long long>> dp(2, vector<long long>(MaxN, 0));
int flag = 0;
dp[flag][0] = 1;
for (int i = 0; i < k.size(); i++)
{
for (int j = 0; j < n; j++)
{
if (k[i] != 'X')
{
dp[!flag][(j * 10 + k[i] - '0') % n] += dp[flag][j];
}
else
{
for (int d = 0; d <= 9; d++)
{
dp[!flag][(j * 10 + d) % n] += dp[flag][j];
}
}
}
fill(dp[flag].begin(), dp[flag].end(), 0);
flag = !flag;
}
printf("%lld\n", dp[flag][0]);
return 0;
}
