问题描述
小C拿到了一个由数字字符和 ? 组成的字符串，她的目标是将所有的 ? 替换成数字字符，使得替换后的字符串表示的十进制整数成为正整数 pp 的倍数。由于方案数可能非常大，需要对最终的结果取模 109+7109+7。
测试样例
样例1：
输入：
s = "??",p = 1
输出：100
样例2：
输入：
s = "????1",p = 12
输出：0
样例3：
输入：
s = "1??2",p = 3
输出：34
题解：
首先想到使用蛮力法硬解，虽然可能会超时，但是先尝试一下，将每个？字符都用0-9替换一遍，然后就果不其然地超时了。
然后想到找出字符串代表数字的最大值与最小值，在其中遍历p的倍数，尝试找出匹配的项，也是蛮力求解。
最后在经过一天的思考后选择了动态规划（确实挺难想的，大概）。定义 dp[i][r] 表示前 i 个字符组成的字符串，其对 p 取模的结果为 r 的方案数。
初始状态：dp[0][0] = 1，空字符串对 p 取模为 0 的方案数为 1。
状态转移方程：
1.当s[i]为数字：
假设当前字符是 digit，则新的模数 new_r 可以通过以下公式计算：
new_r = (r * 10 + digit) % p
更新 dp[i + 1][new_r]：
dp[i + 1][new_r] = (dp[i + 1][new_r] + dp[i][r]) % MOD
2.当s[i]为问号，则从0-9遍历再进行1步骤。
动态规划代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;
const int MOD=1e9+7;
int solution(string s,int p){
int n=s.size();
vector<vector<int>> dp(n+1,vector<int>(p, 0));
dp[0][0]=1;
for(int i=0;i<n;i++){
for(int r=0;r<p;r++){
if(dp[i][r]==0){
continue;
}
if(s[i]=='?'){
for(char c='0';c<='9';c++){
int digit=c-'0';
int new_r=(r*10+digit)%p;
dp[i+1][new_r]=(dp[i+1][new_r]+dp[i][r])%MOD;
}
}
else{
int digit=s[i]-'0';
int new_r=(r*10+digit)%p;
dp[i+1][new_r]=(dp[i+1][new_r]+dp[i][r])%MOD;
}
}
}
return dp[n][0];
}
int main() {
cout << (solution("??", 1) == 100) << endl;
cout << (solution("????1", 12) == 0) << endl;
cout << (solution("1??2", 3) == 34) << endl;
return 0;
}
开始的蛮力法代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;
ll sum=0;
ll mystol(string s){
ll x=0,i=0;
x=s[0]-48;
for(i=1;i<s.size();i++){
x=x*10+(s[i]-48);
}
return x;
}
void cmd(string s, int p) {
// write code here
int i,j;
for(i=0;i<s.size();i++){
if(s[i]=='?'){
for(j=0;j<10;j++){
s[i]=(char)j+48;
//cout << s << "\n";
cmd(s,p);
}
return;
}
}
ll num=mystol(s);
//cout << num << "\n";
if(num%p==0){
sum++;
//cout << "YES" << "\n";
}
return;
}
int solution(string s,int p){
sum=0;
cmd(s,p);
//cout << sum << "\n";
return sum;
}
int main() {
cout << (solution("??", 1) == 100) << endl;
cout << (solution("????1", 12) == 0) << endl;
cout << (solution("1??2", 3) == 34) << endl;
cout << (solution("???1??88745???", 11)) << endl;
return 0;
}
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;
int num[10]={0};
string itos(ll x){
string ans="",t;
while(x>0){
t=(x%10+48);
ans=t+ans;
x/=10;
}
return ans;
}
ll mystol(string s){
ll x=0,i=0;
x=s[0]-48;
for(i=1;i<s.size();i++){
x=x*10+(s[i]-48);
}
return x;
}
ll solution(string s, int p) {
// write code here
string mins=s,maxs=s;
ll i,j,sum=0;
//
for(i=0;i<10;i++){
num[i]=0;
}
for(i=1;i<10;i++){
num[p*i%10]++;
}
for(i=0;i<10;i++){
if(s[s.size()-1]!='?' && num[s[s.size()-1]-48]==0){
return 0;
}
}
//
for(i=0;i<s.size();i++){
if(s[i]=='?'){
mins[i]='0';
}
else{
mins[i]=s[i];
}
}
for(i=0;i<s.size();i++){
if(s[i]=='?'){
maxs[i]='9';
}
else{
maxs[i]=s[i];
}
}
//maxs='1'+ maxs;
ll maxi=0,mini=0;
maxi=mystol(maxs);
mini=mystol(mins);
mini=((mini/p))*p;
//cout << maxi << " " << mini << "\n";
//cout << to_string(1001) << "\n";
string t=" ";
for(j=mini;j<=maxi;j+=p){
//cout << i << "\n";
t=itos(j);
//cout << t << "\n";
while(t.size()<s.size()){
t='0'+t;
}
if(t.size()==s.size()){
for(i=0;i<s.size();i++){
if((s[i]>='0' && s[i]<='9' && s[i]!=t[i])){
break;
}
else if(i==s.size()-1){
sum++;
//cout << t << "\n";
}
}
}
}
//cout << sum << "\n";
ll a=pow(10,9)+7;
sum%=a;
return sum;
}
int main() {
cout << (solution("??", 1) == 100) << endl;
cout << (solution("????1", 12) == 0) << endl;
cout << (solution("1??2", 3) == 34) << endl;
cout << (solution("78???0?7178213?2", 10)==0 ) << endl;
return 0;
}