分饼干

问题描述

易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值

输入描述

输入包括两行：
第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)
第二行为小朋友的人数n

输出描述

输出k可能的数值种数，保证至少为1

输入例子

9999999999999X
3

输出例子

4

分析

首先考虑dfs，但是状态空间太大（10^18），没法穷举。于是考虑用动态规划。

1. 状态表
dp[i][j]，i={0, 1}，状态行；j为余数。dp[i][j]表示当前所有情况下模n余j的数量。

2. 状态转移方程
dp[i][(j * 10 + s[p+1]) % n] += dp[!i][j]，如果我们把前p位当成一个整体s[0:p]，而且知道了dp[!i][0,n]的值，那么对于前p+1位而言，dp[!i][j]的值会贡献到dp[i][(j * 10 + s[p+1]) % n]上。如果s[i+1]的值是X，那么我们只要将s[i+1]遍历10次。

3. 结果项
dp[i][0]

note

状态转移方程其实不是很懂，据说是根据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;
}