AT4802

允许前导 0 何必数位 DP。

顺便滚掉一维。

从这个 $n$ 位数的低位向高位递推。假设现在递推到倒数第 $i$ 位，记 $f_{k:0\to 12}$ 表示从倒数第 $i+1$ 位向后的数字组成的数模 $13$ 余 $k$ 的数有 $f_k$ 个。记 $g_{k:0\to 12}$ 表示从第 $i$ 位向后的数字组成的数模 $13$ 余 $k$ 的数有 $f_k$ 个。

接下来考虑由 $f$ 转移到 $g$：

1. 假如倒数第 $i$ 位不是 ?，是 $x$

   记 $S=10^{i}$，则 $f_k$ 会转移到 $g_{(k+S) \bmod 13}$ 上。循环一遍即可 。

2. 假如倒数第 $i$ 位是 ?

   从 $0$ 到 $9$ 枚举该位，然后每次按照上面的方法做一遍。最后加起来就行。

转移后将 $g$ 赋值给 $f$，重复递推即可。

最终递推完后，答案即 $f_5$

时间复杂度 $O(130n)$。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long rd(){char ch=getchar();long long x=0,f=1;while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
                        while('0'<=ch && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void wr(long long x){if(x<0){putchar('-');x=-x;}if(x>9) wr(x/10);putchar(x%10+'0');}

const long long p=1e9+7;
long long n,f[20],g[20],yu,ans;
char s[100010];

int main(){
	long long i,j,u,v,k;
	scanf("%s",s+1);
	n=strlen(s+1);
	f[0]=1;yu=1;
	for(i=n;i>=1;i--){
		if(s[i]=='?'){
			memset(g,0,sizeof(g));
			for(k=0;k<10;k++){
				v=yu*k;v%=13;
				for(j=0;j<13;j++) g[(j+v)%13]+=f[j],g[(j+v)%13]%=p;
			}
			yu=yu*10;yu%=13;
			for(j=0;j<13;j++) f[j]=g[j],f[j]%=p;
		}
		else{
			v=yu*(s[i]-'0');v%=13;
			yu=yu*10;yu%=13;
			for(j=0;j<13;j++) g[(j+v)%13]=f[j],g[(j+v)%13]%=p;
			for(j=0;j<13;j++) f[j]=g[j],f[j]%=p;
		}
	}
	wr(f[5]%p),putchar('\n');
	return 0;
}