Question

求大神解答下面这道程序问题。。万分感谢，。。

5、津巴布韦
由于计划经济失败，津巴布韦称为世界上通胀率最高的国家。这里的物价即使在一天中也会持续上涨，所以必须实时更新物品价格。例如：1个鸡蛋的价格为35亿津巴布韦元，所以超市做了每位数字的活动标价牌。
钟旭在穆加贝超市打工，有一天遇到了一位比较麻烦的客人。这位客人要退回刚才买走的鸡蛋，但是他不仅丢失了发票，而且连购买鸡蛋的数量也记不清了。鸡蛋价格已经在此期间上涨了1次，所以广告牌上已经写上新的价格。辛亏钟旭还记得如下两件事情。
1）最近一次价格上涨的时候，钟旭只是交换了塑料板的顺序。也就是说，没有添加其他塑料板，也没有去掉过广告牌中的塑料板。
2）看到最近一次上涨的价格时，钟旭心里曾经想过，“哇，这些钱刚好能购买m个糖果”。所以，最后的鸡蛋价格是m的倍数。（因为糖果的价格已经上涨，所以不能计算出鸡蛋的价格了）。
输入
第一行输入测试用例的个数C（C<=50）。之后的C行里面每行输入两个自然数e和m（1<=e<=1014，2<=m<=20）。当前鸡蛋的价格不能以0开始，但是之前的价格可以以0开始。
输出
每个测试用例在1行内输出可能的价格个数除以1 000 000 007的余数。

示例输入值：
4
321 3
123 3
422 2
12738173912 7
示例输出值
5
0
2
11033
示例输入输出值的说明
第一个示例输入值：以前鸡蛋的价格可能是123元、132元、213元、231元、312元。
第二个示例输入值：无论怎样重新排列123元的数字，结果都会比123元大，故无解。
第三个示例输入值：224元和242元是可能的价格。
第四个示例输入值：鸡蛋简直太贵了
每个测试用例在1行内输出可能的价格个数除以1 000 000 007的余数。

Answer 1

// 求将e重排后小于e且是m倍数的个数

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;

int count(string e, int m) { // 方法一，暴力搜索    
    ll cnt = 0;
    string s = e; // 遍历每个小于e的排列s
    sort(s.begin(), s.end()); // 升序后为最小的排列
    while (s != e) { // 保证s小于e
        ll num = stoll(s); // 转为长整数
        if (num % m == 0) // 判断其是否为m的倍数
            ++cnt;
        next_permutation(s.begin(), s.end()); // 库函数取下个排列
    }
    return cnt % mod;
}

int dp_count(string e, int m) { // 方法二，状态压缩动态规划
    int n = e.length();
    int a[n]; // 保存e各数位值
    for (int i = 0; i < n; ++i)
        a[i] = e[i] - '0';
    int size = 1 << n; // 总状态数，每个状态二进制为1的位对应该数是否被选择
    ll dp[size][m][2]; // i状态组合中模m余j且小于a的排列个数
    // 状态i的二进制表示中1的个数d表示下一数位最终对应a[d]
    // 第3维为0表示当前位为止有数位小于a中对应位数值，下一数位可任取
    // 为1表示当前位为止所有数位都与a中对应位数值相等，下一数位不能大于a[d]
    memset(dp, 0, sizeof(dp));
    dp[0][0][1] = 1; // 初始条件，最高位值不能大于a[0]
    for (int i = 0; i < size; ++i) { // 遍历各组合状态
        for (int j = 0; j < m; ++j) { // 遍历各余数
            for (int p = 0; p < 2; ++p) { // 当前为止是否有数位小于对应a[d]
                if (dp[i][j][p] == 0)
                    continue; // 计算过的状态上继续添加数位
                int vis[10] = {0}; // 防止重复计算
                for (int k = 0; k < n; ++k) { // 添加数a[k]为下一数位
                    if ((i & (1 << k)) || vis[a[k]])
                        continue; // 跳过已选择以及重复的数
                    int d = __builtin_popcount(i); // a[k]最终对应为a[d]
                    // 注意a[k]每次添加到末尾，所以状态转移中余数变为(j*10+a[k])%m
                    if (p == 0) { // 下一数位可取a中的任意值
                        dp[i|(1<<k)][(j*10+a[k])%m][0] += dp[i][j][0];
                        vis[a[k]] = 1;
                    }
                    else if (a[k] <= a[d]){ // 下一数位取值不能超过a[d]
                        if (a[k] == a[d])
                            dp[i|(1<<k)][(j*10+a[k])%m][1] += dp[i][j][1];
                        else
                            dp[i|(1<<k)][(j*10+a[k])%m][0] += dp[i][j][1];
                        vis[a[k]] = 1;
                    }
                }
            }
        }
    }
    return dp[size - 1][0][0] % mod;
}

int main() {
    int C;
    cin >> C;
    while (C--) {
        string e;
        int m;
        cin >> e >> m;
        //cout << count(e, m) << "\n";  // 暴力搜索会超时
        cout << dp_count(e, m) << "\n"; // 建议使用动态规划
    }
    return 0;
}

g++编译通过，程序运行结果与示例相符

望采纳，谢谢～

追问

最后一组答案怎么不对？求答。

追答

可能你的编译器平台是32位，将long int解释为了4个字节，可将原答案中的strtol换成strtoll。现已对原答案进行修改，改为了C++语言，并添加了动态规划解法。

Answer 2

居然不能直接回复两个字母真是太让人失望了CAInteger:整型,0~65535Double:双精浮点,比较大~但是不是整形Long:长整型，比整型长Currency:也是个浮点，貌似Or:逻辑或，同假为假，同真为真，其他为真Xor:异或，同假为真，同真为假,其他为真And:逻辑与，同假为假，同真为真，其他为假Not:非运算,这个不能用在两个表达式之间~~也就是不能truenottrue