問題描述

易老師購買了一盒餅干，盒子中一共有k塊餅干，但是數(shù)字k有些數(shù)位變得模糊了，看不清楚數(shù)字具體是多少了。易老師需要你幫忙把這k塊餅干平分給n個小朋友，易老師保證這盒餅干能平分給n個小朋友?，F(xiàn)在你需要計(jì)算出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é)果項(xiàng)
dp[i][0]

note

狀態(tài)轉(zhuǎn)移方程其實(shí)不是很懂，據(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;
}