网易2017春招笔试分饼干

本文主要是介绍网易2017春招笔试分饼干，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值
输入描述:
输入包括两行：
第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)
第二行为小朋友的人数n

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

输入例子:
9999999999999X
3

输出例子:
4

测试用例:
9XXXXXXXXXXXXXXXXX
1
对应输出应该为:
100000000000000000

测试用例:
3X8XXX99X04XXXXX7X
8543

对应输出应该为:

11705428

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;
//核心：动态规划.从低位到高位,自底向上求解. 原理:若c=a+b,则c%n = （a%n + b%n） % n  int main(){int n;string s;//第一行输入的饼干数 cin>>s; scanf("%d",&n);//第二行输入的人数 long long dp[n+1],temp[n+1];//dp[i]表示余数为i的总共的可能数目.temp是dp的备份，防止状态转移混乱memset(dp,0,sizeof(dp));//dp数组置0 //先假设X位为0,根据其他已定位计算饼干数num //之后再调整X long long num=0;int le=s.size()-1;//le为s长度 for(int i=le;i>=0;i--){if(s[i]!='X')num=(s[i]-'0')*(long long)pow(10.0,le-i)+num;//num表示所有X位都默认为0的饼干数                }int i=le;//从低位向高位找第一个为X的位置，用于dp初始化for(;i>=0;i--)if(s[i]=='X')break;for(int j=0;j<=9;j++){//遍历X从0到9的情况 long long tmp=(j*(long long)pow(10.0,le-i));int pos=(num+tmp)%n;//取余 dp[pos]+=1;//余数为pos的计数+1 }i--;//调整X //从低位向高位继续遍历,找数位为X的位 for(;i>=0;i--){if(s[i]=='X'){memset(temp,0,sizeof(temp));//temp数组置0 for(int j=0;j<=9;j++){//遍历X从0到9的情况 long long tmp=(j*pow(10.0,le-i));//计算增量 int pos=tmp%n;//计算增量的模n余数 //遍历dp[] for(int p=0;p<n;p++){temp[(p+pos)%n]+=dp[p];//核心,递归方程}}      for(int p=0;p<n;p++)//对一个X迭代完成后,temp写入dp dp[p]=temp[p];                  }      }cout<<dp[0]<<endl;return 0;
}