首页 > 试题广场 >

分饼干

[编程题]分饼干
  • 热度指数：2196 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值

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


输出描述:
输出k可能的数值种数，保证至少为1
示例1

输入

9999999999999X 3

输出

4
算法知识视频讲解
添加回答
Java
张瑞泽头像 张瑞泽
简单介绍原理：
1234%7=1000%7+200%7+30%7+4%7.
1X3X%20=1000%20 + X*100%20 + 30%20 + x%20
(x=0-9)

代码如下：
import java.util.*;

public class Main {


    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {

            String s = in.nextLine();

            String s2 = in.nextLine();

            int n = Integer.parseInt(s2);

            long d[] = new long[n];//n children

            boolean dLoaded = false;


            long base = 1;

            long sum = 0;


            //假入给了99X9，base就是10000。(暂时多了一位），用于之后对每一位数字进行求余。

            for (int j = 0; j < s.length(); j++) {

                base *= 10;

            }


        //遍历每一位数字。

            for (int i = 0; i < s.length(); i++) {

        //对base除以10，为下一位求余做准备。

                base /= 10;

                if (s.charAt(i) == 'X') {

                    if (!dLoaded) {

                    //如果记录余数的数组d还没初始化过，就先把这次的计算作为初始化的值。

                        long[] temp = new long[n];

                        //统计余数的数组。长度为n，下标是0~n-1，表示 对应可以得到对应余数的个数。

                        for (int j = 0; j <= 9; j++) {

                            temp[(int) ((j * base) % n)]++;

                        }

                           //temp数组复制到d数组上。这里idea优化成如下方法，效率更高。d数组便初始化过了。跳过后面部分

                        System.arraycopy(temp, 0, d, 0, n);

                        dLoaded = true;

                        continue;

                    }

                    //如果初始化了d数组，则在新发现X时，需要把新的余数统计结果和原来的统计结果d进行汇总

                    int[] mod = new int[10];

                        //因为x有10种可能，所以最多产生10个余数，而如果采用new int[n]来统计的话，n可能远大于10，所以效率会差很多。mod记录了每个可能的数字所产生的余数。

                    for (int j = 0; j <= 9; j++) {

                        mod[j] = (int) ((j * base) % n);

                    }

                    //将新的统计结果mod和原来的统计结果d进行融合。原理如下：newd的下标对应产生的余数，比如newd[2]代表余数为2的所有可能性总数。于是对于newd[m]，其可能性总数便来自于 sum{d[m-mod[k]]}（仔细想一下，mod[k]是这次产生的新余数，m是要统计的目标余数），+n和%n是为了防止负数情况。

                    long[] newd = new long[n];

                    for (int m = 0; m < n; m++) {

                        for (int k = 0; k <= 9; k++) {

                            newd[m] += d[(n + m - mod[k]) % n];

                        }

                    }

                    System.arraycopy(newd, 0, d, 0, n);

                } else {

                //如果不是x，就按最开始处讲的原理直接求余并累加进去即可。

                    long a = (s.charAt(i) - '0') * base;

                    sum = (sum + a) % n;

                }

            }

            //常数位累加后的余数是sum，而我们要能整除的所有可能性，也就是余数为0的所有可能性，所以取d数组中的n-sum对应的可能性即可。为何%n?比如n=7，sum=0，n-sum=7，d[7]显然越界。实际上此时应该去访问d[7%7]=d[0]

            System.out.println(d[(int) ((n - sum) % n)]);

        }

    }

}

编辑于 2017-04-11 09:51:38 回复(5)
JacobGo！头像 JacobGo！ 
package go.jacob.day918;

import java.util.Scanner;

/**
 * [编程题]分饼干
 * 
 * @author Jacob 
 * Long表示范围为-9223372036854775808到9223372036854775807（19位）
 */
public class Demo1 {
    /*
     * 动态规划求解
     * 用暴力解***超时
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int len = s.length();
        int n = sc.nextInt();
        // dp[i][j]表示前i位（高位开始）余数为j的个数
        long[][] dp = new long[len + 1][n];
        dp[0][0] = 1;// 初始化
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < n; j++) {
                // 如果当前位为X，用0-9带入
                if (s.charAt(i) == 'X') {
                    for (int k = 0; k <= 9; k++) {
                        dp[i + 1][(j * 10 + k) % n] += dp[i][j];
                    }
                } else {// 如果当前位上的数字为不为X，用具体值带入
                    dp[i + 1][(j * 10 + s.charAt(i) - '0') % n] += dp[i][j];
                }
            }
        }
        System.out.println(dp[len][0]);
        sc.close();
    }
}

发表于 2017-09-18 10:24:05 回复(0)
古典文化头像 古典文化
C++: 
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
	string s;
	int n;
	while (cin >> s >> n){
		int len = s.length();
		vector<vector<long long int>> dp(len + 1, vector<long long int>(n, 0));
		dp[0][0] = 1;
		for (int i = 1; i <= s.length(); i++){
			for (int j = 0; j < n; j++){
				if (s[i - 1] == 'X'){
					for (int k = 0; k < 10; k++){
						int newJ = (j * 10 + k) % n;
						dp[i][newJ] += dp[i - 1][j];
					}
				}
				else{
					int newJ = (j * 10 + (s[i - 1] - '0')) % n;
					dp[i][newJ] += dp[i - 1][j];
				}
			}
		}
		cout << dp[len][0] << endl;
	}
	return 0;
}
java: 
import java.util.*;
public class Main{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			String s = in.nextLine();
			int n = in.nextInt();
			int len = s.length();
			long long[][] dp = new long long[len + 1][n];
			dp[0][0] = 1;
			for(int i = 1; i <= len; i++){
				for(int j = 0; j < n; j++){
					if(s.charAt(i - 1) == 'X'){
						for(int k = 0; k <= 9; k++){
							int newJ = (j * 10 + k) % n;
							dp[i][newJ] += dp[i - 1][j];
						}
					}
					else{
						int newJ = (j * 10 + (s.charAt(i - 1) - '0')) % n;
						dp[i][newJ] += dp[i - 1][j];
					}
				}
			}
			System.out.println(dp[len][0]);
		}
		in.close();
	}
}

发表于 2017-06-27 14:18:31 回复(0)
Python
周昆头像 周昆
上一个python版本的动态规划。 
# -*- coding: utf-8 -*-
# 输入k,n
k = raw_input() 
n = int(raw_input())
remainders = [1] + [0] * (n - 1)

for i, s in enumerate(k):
	temp = [0] * n
	if s != 'X':
		s = int(s)
		for j in range(n):
			temp[(j*10+s) % n] += remainders[j]
	else:
		for s in range(10):
			for j in range(n):
				temp[(j*10+s) % n] += remainders[j]
	remainders = temp
print remainders[0]

发表于 2017-04-14 11:27:20 回复(1)
为啥要起名字头像 为啥要起名字
k=raw_input().strip()
n=int(raw_input().strip())
dp=[[0]*n for j in range(len(k)+1)]
dp[0][0]=1
for i in range(1,len(k)+1):
    for j in range(n):
            for w in range(10):
                if k[i-1]=='X' or int(k[i-1])==w:
                    dp[i][(j*10+w)%n]+=dp[i-1][j]
                    #不管中间的j为多少，我只要保证最后j为0
print(dp[len(k)][0])
发表于 2018-05-18 16:35:40 回复(0)
牛客2793674号头像 牛客2793674号 

	/*





	dp[i][j]表示长度为i的数 除以小朋友的人数之后得到的余数为j的个数 





	dp[i][newJ] = dp[i-1][j], s[i] != 'X', newJ = (j*10+s[i]-'0')%n;





	              dp[i-1][j], s[i] == 'X', newJ = (j*10+k)%n, k=0~9





	*/





	import java.util.*;





	public class Main {





	 





	    public static void main(String[] args) {





	        // TODO Auto-generated method stub





	        Scanner scan = new Scanner(System.in);





	        while(scan.hasNext()){





	            String s= scan.nextLine();           





	            int n = scan.nextInt();





	             





	            long[][] dp = new long[s.length()+1][n];





	            dp[0][0] = 1;





	            for(int i=1; i<=s.length(); i++)





	                for(int j=0; j<n; j++){





	                    if(s.charAt(i-1) == 'X'){





	                        for(int k=0; k<=9; k++){





	                            int newJ = (j*10+k)%n;





	                            dp[i][newJ] += dp[i-1][j];





	                        }





	                    } else{





	                        int newJ = (j*10+s.charAt(i-1)-'0')%n;





	                        dp[i][newJ] += dp[i-1][j];





	                    }





	                     





	                }





	            System.out.println(dp[s.length()][0]);





	             





	        }





	    }





	 





	}

编辑于 2017-08-01 16:18:29 回复(0)
魅影骑士头像 魅影骑士 

	#include <bits/stdc++.h>





	





	using namespace std;





	





	longlongn1[10001], n2[10001];





	intmain(){





	string s;





	intn;





	cin >> s >> n;





	longlongret = 0;





	n1[0] = 1;





	for(inti = 0; i < s.size(); i++){





	memset(n2, 0, sizeof(n2));





	for(intj = 0; j < n; j++){





	for(intk = 0; k < 10; k++){





	if(isdigit(s[i]) && s[i] - '0'!= k) continue;





	n2[ ( ( j * 10) + k ) % n] += n1[j];





	}





	}





	memcpy(n1,n2,sizeof(n1));





	}





	cout << n1[0] << endl;





	}
分析：枚举每个位置的数字,然后记录满足要求的答案数就可。
编辑于 2017-03-25 20:09:39 回复(2)
☠头像 ☠
### 分析
显然数字太大我们不能直接计算模(超过long long)，而且也不能枚举X(否则空间可能有$10^{18}$)。不过我们考虑到模n应该不大（喂喂，怎么题目没有给n的范围啊～），因此可以考虑用动态规划的思想从这里入手。
用$mod[k]$表示当前所有情况下模n余k的数量。如果我们把前i位当成一个整体$s[0:i]$，而且知道了$mod[0:n]$的值，那么对于前i+1位而言，$mod[k]$的值会贡献到$mod[(k*10+s[i+1])mod\\%n]$上。如果$s[i+1]$的值是X，那么我们只要将$s[i+1]$遍历10次。
总体上说，就是从前往后遍历，依次更新mod数组，最后的结果当然就是$mod[0]$了。
注意long long 。

### 我的答案
```cpp 
#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 100000
void transform1(long long mod[],int n){
    long long tmpMod[MAXN]={0};
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++){
            tmpMod[(i*10+j)%n]+=mod[i];
        }
    }
    memcpy(mod,tmpMod,sizeof tmpMod);
}
void transform2(long long mod[],int k,int n){
    long long tmpMod[MAXN]={0};
    for(int i=0;i<n;i++){
        tmpMod[(i*10+k)%n]+=mod[i];
    }
    memcpy(mod,tmpMod,sizeof tmpMod);
}
int main(){
    long long mod[MAXN]={0};
    string s;
    int n;
    cin>>s>>n;
    mod[0]=1;
    for(int i=0;i<s.length();i++){
        if(s[i]=='X'){
            transform1(mod,n);
        }else{
            transform2(mod,s[i]-'0',n);
        }
    }
    cout<<mod[0]<<endl;
}
```

编辑于 2017-03-31 13:18:07 回复(4)
HelloHello233头像 HelloHello233
dp：状态转移方程dp[i][newJ] += dp[i-1][J].其中i代表数字串的长度，J代表余数，结果值代表i长度的数字串中求余n余J的所有可能结果总数
根据以上的说明，显而易见newJ==(J*10+k)%n ，k代表当前数字串中个位的值（也就是数字串的第i位）
以下两段代码均经过测试可AC，如果去除if条件判断，则程序运行的结果为：输入长度为n的字符串，则求出长度为n的数字串中，求余n余数为0的所有结果总数，但题意不是这么要求的，所以枚举的时候，需要进行判断，如果判断到X则可以枚举0~10（也就是k的值可以取值为0~10），如果不是X，则k只能取值为数字串中的对应值，举个栗子：
如果输入的数字串长度为3，不加if判断的话，则枚举到的所有结果为：0~999
如果加了判断，如X33X，则枚举到的结果值为330~339,1330~1339 ... 1339~9339 符合题意
在以上枚举到的结果中，进行求余判断并且记录结果，篇幅有限，不说太多细节，关键是要理解好状态转移方程 
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	String str = sc.next();
    	int n = sc.nextInt();
    	long[][] dp = new long[str.length()+1][]; //不用long的话通过率只能为90%
    	for(int i = 0;i<=str.length();i++){
    		dp[i] = new long[n];
    	}
    	dp[0][0] = 1;
    	for(int i = 1;i<=str.length();i++){
    		char c = str.charAt(i-1);
    		for(int j = 0;j<n;j++){
    			for(int k = 0;k<10;k++){
    				if(c=='X'||c=='0'+k){
    					dp[i][(j*10+k)%n]+=dp[i-1][j];
    				}
    			}
    		}
    	}
    	System.out.println(dp[str.length()][0]); 
    }
}
//以上发现第i行的值只会访问到第i-1行的值，所以实际只需要两个数组即可，优化空间之后的代码：
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	String str = sc.next();
    	int n = sc.nextInt();
    	long[] dp = new long[n];     	
    	dp[0] = 1;
    	for(int i = 1;i<=str.length();i++){
    		char c = str.charAt(i-1);
    		long[] tmp = new long[n]; 
    		for(int j = 0;j<n;j++){
    			for(int k = 0;k<10;k++){
    				if(c=='X'||c=='0'+k){
    					tmp[(j*10+k)%n]+=dp[j];
    				}
    			}
    		}
    		dp = tmp;
    	}
    	System.out.println(dp[0]);
    }
}

发表于 2017-04-03 11:53:41 回复(2)
哟，我喜欢头像 哟，我喜欢
发表于 2019-07-20 14:21:06 回复(0)
系的呀头像 系的呀
let count = 0
function test(number, people) {
    number = number + ''
    if (number.indexOf('X') === -1) {
        return
    }
    for (let i = 0; i < 10; i++) {
        let number2 = number.substr(0, number.indexOf('X')) + i + number.substr(number.indexOf('X') + 1, number.length)

        if (!isNaN(number2) && number2 % people == 0) {
          
            count = count + 1
        } else {
            test(number2, people)
        }

    }
}
let number = readline()
let people = readline()
test(number, people)
console.log(count)
发表于 2018-08-24 10:45:39 回复(0)
张康.头像 张康. 
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();//模糊数值
        int n = sc.nextInt();//小朋友个数
        long[][] dp = new long[s.length() + 1][n];//dp[i][j]表示前i个字符串表示的整数除n后余数为j的总数。
        dp[0][0] = 1;
        for(int i = 1; i <= s.length(); i++) {
            for(int j = 0; j < n; j++) {
                char c = s.charAt(i - 1);
                if(c == 'X') {
                    //当前字符为X的时候，和下面的分析同理。只是当前位置的数字不是固定的，可能是0-9中的任何一个。
                    for(int k = 0; k <= 9 ;k++) {
                        dp[i][(10 * j + k) % n] += dp[i - 1][j];
                    }
                }
                else {
                    //前i-1字符串组成的整数 除n得的余数为j的情况有dp[i - 1][j]种，余数只能在0到n-1的范围
                    //假设前i-1字符串组成的数是125，n=4，余数为125 % 4 = 1，
                    //所以dp[3][0]=0,dp[3][1]=1,dp[3][2]=0,dp[3][3] = 0
                    //假设第i个字符为6，所以新的数变成1256，1256 % n就相当于(125 * 10 + 6) % n
                    //相当于[(124 + 1)*10 + 6] % n,因为前i-1个组成的数中125 % n = 1，所以(125 - 1) * 10是能除尽n的
                    //所以就相当于[(1 * 10) + 6] % n ,而 1 就是前i-1个组成的数除n得到的余数，所以前i-1个组成的数除n有多少个余
                    //数为1的情况，那么前i个组成的数就有多少种余数为[(1*10) + 6] % n 的情况。
                    //for(int j = 0; j < n; j++) 此for循环中的j代表前i-1个组成的数除n得到的余数，余数从0到n-1
                    dp[i][(10 * j + c - '0') % n] += dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[s.length()][0]);
    }
}
发表于 2018-04-14 12:14:43 回复(0)
逗比请来的猴子头像 逗比请来的猴子 
import java.util.Scanner;

/*
 * 参考大神的解题思路：
 *
 * https://www.nowcoder.com/questionTerminal/44d0ee89b51b4725b403d1df2381d2b2
 * 显然此题直接暴力会超时，10^18中可能情况，考虑使用动态规划
 * dp[i][j]表示前i个字符串对应整数mod n之后余数为j的情况数
 * 如果当下字符为X，则可以遍历0-9重新进行计算；
 * 否则可以具体计算出dp值
 * */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String line = scanner.next();
            int n = scanner.nextInt();
            int len = line.length();
            long[][] dp = new long[len + 1][n];
            dp[0][0] = 1;
            for (int i = 1; i <= len; i++) {
                for (int j = 0; j < n; j++) {
                    char c = line.charAt(i - 1);
                    if (c == 'X') {
//                        0-9进行遍历
                        for (int k = 0; k < 10; k++) {
                            dp[i][(j * 10 + k) % n] += dp[i - 1][j];
                        }
                    } else {
//                        直接计算
                        dp[i][(j * 10 + c - '0') % n] += dp[i - 1][j];
                    }
                }
            }
            System.out.println(dp[len][0]);
        }
    }
}
发表于 2018-04-11 20:42:23 回复(0)
andy201801191118182头像 andy201801191118182
走的是穷举思路，有1个X比较10次有2个 比较100次，有3个X就是1000次，以此类推。
比如1xxx5个饼干平分给5个人或者3个人  都是比较1000次 
也许有什么好的办法不用比较这么多次，用数学的算法来判断？

public static char[] iii ={'0','1','2','3','4','5','6','7','8','9'};
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.nextLine();
            String s2 = in.nextLine();
            char[] ss=s.toCharArray();
            int count=0;
            for (char c : ss) {
                if(!Character.isDigit(c)){
                    count++;
                }
            }
            if (count==0) {
                return;
            }
            Integer leng=Integer.valueOf(s2);
            int c=0;
            double dou= Math.pow(10, count);
            for (int j = 0; j < dou; j++) {
                Integer jie= tihuan(s, j, count);
                if (jie%leng==0) {
                    System.out.println("可以整除"+leng+"的数字："+jie);
                    c++;
                }
                if (j==dou) {
                    System.out.println("aaa");
                }
            }
            System.out.println("次数："+c);
        }
    }
    //整理数字 将数字替换原来的字母
    public static Integer tihuan(String s,Integer i,int count) {
        char[] c =ii(i, count).toCharArray();
        char[] ss =s.toCharArray();
        int sss=0;
        for (int j = 0; j < ss.length; j++) {
            if(!Character.isDigit(ss[j])){
                int x= Integer.valueOf(String.valueOf(c[sss]));
                ss[j]=iii[x];
                sss++;
            }
        }
        return Integer.valueOf(String.valueOf(ss));
    }
    //补齐0
    public static String ii(Integer i,int count) {
        String s=i.toString();
        while (!(s.length()>=count)) {
            s="0"+s;
        }
        return s;
    }

发表于 2018-01-19 11:35:20 回复(0)
王智宏基头像 王智宏基 
#include <bits/stdc++.h>
using namespace std;

using ulli = unsigned long long int;

ulli doit(vector<ulli>& vec, ulli total, ulli n) {
    vector<vector<ulli>> dp = vector<vector<ulli>>(vec.size() + 1, vector<ulli>(n, 0));    // dp[i][j] means how many kinds of combination when check i , remain is j
    if (vec.empty()) {return total % n == 0;}
    dp[0][total] = 1;
    for (int i = 0; i < dp.size() - 1; i++) {
        for (ulli j = 0; j < n; j++) {
            if (dp[i][j] == 0) { continue;}
            for (int k = 0; k < 10; k++) {
                ulli newremain = (j + (k * vec[i])) % n;
                dp[i + 1][newremain] += dp[i][j];
            }
        }
    }
    return dp[vec.size()][0];
}

int main() {
    string oneline;
    //while (getline(cin, oneline)) {
    cin >> oneline;
    ulli n;
    cin >> n;
    ulli base = 0;
    ulli digit = 1;
    vector<ulli> mode_remain_of_digits_of_x;
    for (int i = oneline.size() - 1; i >= 0; i--) {
        if (oneline[i] == 'X') {
            mode_remain_of_digits_of_x.push_back(digit % n);
        } else {
            base += digit * (oneline[i] - '0');
        }
        digit *= 10;
    }
    ulli total = base % n;
    cout << doit(mode_remain_of_digits_of_x, total, n) << endl;
    //}
}
编辑于 2017-09-10 13:22:22 回复(0)
小萌燕头像 小萌燕 
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int n;
	cin>>n;
	//d[i][j]表示前i位%n的结果
	long long  d[20][10000];
	memset(d,0,sizeof(d));
	d[0][0]=1;
	int len=s.size();
	for(int i=1;i<=len;i++)
		for(int j=0; j<n;j++)
			if(s[i-1]=='X')
			{
				for(int k=0;k<=9;k++)
				{
					int newj=(j*10+k)%n;
					d[i][newj]+=d[i-1][j];
				}
			}
			else 
			{
				int newj=(j*10+(s[i-1]-'0'))%n;
				d[i][newj]+=d[i-1][j];
			}
	cout<<d[len][0]<<endl;
	return 0;
}
http://www.cnblogs.com/qqky/p/6939788.html
找到的最简单容易理解的一种方法，链接如上
发表于 2017-08-11 14:13:47 回复(0)
潇潇古月头像 潇潇古月 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            int n = Integer.parseInt(sc.nextLine());
            long[][] dp = new long[s.length()+1][n];
            dp[0][0] = 1;
            for (int i = 1; i <= s.length(); i++) {
                if(s.charAt(i-1) == 'X') {
                    for (int k = 0; k < 10; k++) {
                        int ret = (int)((Math.pow(10, s.length() - i) * k) % n);
                        for (int j = 0; j < n; j++) {
                            dp[i][j] += dp[i-1][(j + n - ret) % n];
                        }
                    }
                } else {
                    int ret = (int) ((Math.pow(10, s.length() - i) * (s.charAt(i-1) - '0')) % n);
                    for (int j = 0; j < n; j++) {
                        dp[i][j] += dp[i-1][(j + n - ret) % n];
                    }
                }
            }
            System.out.println(dp[s.length()][0]);
        }
    }
}


发表于 2017-07-28 10:57:41 回复(0)
有人＠你头像 有人＠你 
#include <iostream>
#include <string>
using namespace std;

void findans(string &s,int &countx,int n,int t){
	if(t==s.length()){
		int num=atoi(s.c_str());
		if (num%n == 0)
			countx++;
		return;
	}
	if(s[t]=='X'){
		for(int i=0;i<=9;i++){
			s[t]=i+'0';
			findans(s,countx,n,t+1);
			s[t]='X';
		}
	}
	else
		findans(s,countx,n,t+1);
}

int main(int argc, char const *argv[])
{
	string s;
	cin>>s;
	int n;
	cin>>n;
	int countx=0;
	findans(s,countx,n,0);
	cout<<countx<<endl;
	return 0;
}

//请教各位，递归穷举为什么会超时

发表于 2017-07-25 21:14:48 回复(3)
C/C++
Archerxyz头像 Archerxyz
//DP[第几个X][余数为k时的可能个数]
//从小到大地算X对余数的改变
//由第k个X所能得出的可能由X=0到X=9 与 第k-1个X的累加所得。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
long long DP[18][100000]; 
int main()
{
string s;
cin >> s ;
int n;
cin >> n ;
long long sum=0;
long long mi=1;
vector<long long> Xset;
for (int i = s.size() -1 ; i>=0 ; i--)
{
if (s[i]>='0' && s[i] <= '9')
{
sum+= (s[i] - '0') * mi;
mi*=10;
}

if (s[i] == 'X')
{
Xset.push_back(mi);
mi*=10;
}
}
   int aa = sum%n; //除去X外，其他给出的数字能够确定一个余数。

DP[0][aa] = 1;
    
//第一行 处理第一个X且其他X都设为0
for (int k = 1; k<10 ; k++)
{
DP[0][(aa + Xset[0] * k)%n] ++ ;
}
//逐次遍历其他X。 X的个数，令上个X中的DP为基数。
for (int j = 1; j < Xset.size(); j ++)
{
for (int k = 0; k<10 ; k++)
{
for (int i = 0 ; i < n ; i++)
{
DP[j][(i + Xset[j] * k)%n] += DP[j-1][i] ; 
}
}
}
cout << DP[ Xset.size() - 1][0] << endl;
        

return 0;
}
发表于 2017-05-18 05:10:11 回复(0)
提交观点

问题信息

动态规划
来自：网易2017春招笔试真...
难度：
19条回答 11489浏览

热门推荐

通过挑战的用户

相关试题

分饼干

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号