[编程题]分饼干
- 热度指数：2193 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值
输入描述:
输入包括两行：
第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)
第二行为小朋友的人数n
输出描述:
输出k可能的数值种数，保证至少为1
示例1
输入
9999999999999X 3
输出
4
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)
简单介绍原理：
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)
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版本的动态规划。
# -*- 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:
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)
/*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 stubScanner 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)
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)
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)
走的是穷举思路，有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;
}
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;
}
发表于 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)
//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)
问题信息
通过挑战的用户
-
2022-07-12 19:56:10
-
2022-07-06 11:13:00
-
2021-08-23 11:25:54
-
2021-04-02 13:51:50 -
2021-03-23 21:28:34
相关试题
-
评论(153) 来自网易2017春招笔试真题...
-
评论(79) 来自网易2017春招笔试真题...
-
评论(36) 来自网易2017春招笔试真题...
-
评论(79) 来自网易2017春招笔试真题...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
