题目链接：http://acm./problem/4002
博客园食用链接：/lonely-wind-/p/13437112.html
Description
对于一个正整数S,我们可以看成 S = { s n , s n − 1 , . . . . . . , s i , . . . . . . s 1 } S = \{s_n,s_{n-1},......,s_i,......s_1\} S={sn,sn−1,......,si,......s1},其中 s i = ⌊ S 1 0 i − 1 ⌋ m o d 10 s_i = \lfloor \frac S {10^{i-1}} \rfloor \mod\ 10 si=⌊10i−1S⌋mod10
我们定义两个整数的#运算: S # T = { ( s n ∗ t n + p r e n ) m o d 10... , ( s 1 ∗ t 1 + p r e 1 ) m o d 10 } S \# T=\{(s_n*t_n+pre_n)mod\ 10...,(s_1*t_1+pre_1)mod\ 10\} S#T={(sn∗tn+pren)mod10...,(s1∗t1+pre1)mod10}
其中 p r e i = { 0 i = 1 ( s i − 1 ∗ t i − 1 + p r e i − 1 ) / 10 1 ≤ i ≤ n pre_i=\left\{\begin{matrix} 0 & i=1\\ (s_{i-1}*t_{i-1}+pre_{i-1})/10 & 1\leq i\leq n \end{matrix}\right. prei={0(si−1∗ti−1+prei−1)/10i=11≤i≤n
如果你了解过两个整数的加法,#运算与加法类似,不过每一位相加变成了每一相乘,并且最后的结果只保留后n位
例如: 123 # 23 = 49 , 258 # 24 = 132 , 423 # 523 = 49 123\ \# \ 23 =49,258\ \# \ 24 = 132,423\ \# \ 523=49 123#23=49,258#24=132,423#523=49
现在,你有一个长度为n的整数AA,你能否求出存在多少种长度为n的正整数BB,满足 A # B = A A \ \# \ B = A A#B=A,结果对 998244353 998244353 998244353取模.
PS: A A A和 B B B都可能存在前导零
Input
第一行一个整数 n ( 1 ≤ n ≤ 2 e 5 ) n(1\leq n \leq 2e5) n(1≤n≤2e5),表示正整数的长度
第二行一个长度为n的正整数 A A A,表示所给的正整数
Output
一行一个整数,表示结果.
Sample Input 1
2
13
Sample Output 1
1
Sample Input 2
3
205
Sample Output 2
20
Sample Input 3
4
3217
Sample Output 3
2
emmm，这题是个DP，维数也知道是个2维的。。。但一直不知道 d p [ i ] [ j ] dp[i][j] dp[i][j]表示的是什么，后面被大佬一提醒。。。 j j j可以表示进位的位数！哦！恍然大悟，然后劈里啪啦一顿乱敲。
我们可以用 d p [ i ] [ j ] dp[i][j] dp[i][j]表示为第 i i i位给第 i + 1 i+1 i+1位进了 j j j位的时候的方案数，那么对于第一位进行的初始化如下：
for (int i=0; i<=9; i++) {if (i*s[1]%10==s[1]) dp[1][i*s[1]/10]++;}
然后从第二位开始进行转移，那么怎么转移呢？对于位置肯定是要枚举的，对于当前位置要放什么数（如上所写）似乎也不能避免枚举，那么现在能够进行DP吗？似乎不太行，因为我们不知道上一位的进位是多少，那么就没办法转移，所以我们还要对上一位的进位进行枚举。那么就可以得到如下方程：
for (int i=2; i<=n; i++)for (int j=0; j<=9; j++)//枚举当前放置的数for (int k=0; k<=9; k++)//枚举上一位的进位/*DP*/
DP的话一定是在方案合理的情况下生成的，也就是说 ( s [ i ] ∗ j + k ) % 10 (s[i]*j+k)\%10 (s[i]∗j+k)%10必须还是 s [ i ] s[i] s[i]，那么似乎转移也就出来了： d p [ i ] [ ( s [ i ] ∗ j + k ) / 10 ] = ( d p [ i ] [ ( s [ i ] ∗ j + k ) / 10 ] + d p [ i − 1 ] [ k ] ) % m o d dp[i][(s[i]*j+k)/10]=(dp[i][(s[i]*j+k)/10]+dp[i-1][k])\%mod dp[i][(s[i]∗j+k)/10]=(dp[i][(s[i]∗j+k)/10]+dp[i−1][k])%mod
那么最后的答案好像就是 d p [ n ] [ 0 ] dp[n][0] dp[n][0]了，不过。。。显然不太对，最高位实际上进多少位都没关系，反正不参与计算的，所以最后的答案是 ∑ i = 0 9 d p [ n ] [ i ] \sum_{i=0}^{9}dp[n][i] ∑i=09dp[n][i]。
不过需要注意的是，出题人提醒了一下前导零。。。。不提醒还好，一提醒我就把前导零删了。。。前导零是不能删的！！！也就是说0013得出的结果是100
以下是AC代码：
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mac=2e5+10;const int mod=998244353;char ss[mac];int s[mac];ll dp[mac][10];int main(int argc, char const *argv[]){int n;scanf ("%d",&n);scanf ("%s",ss+1);for (int i=1; i<=n; i++) s[i]=ss[n-i+1]-'0';for (int i=0; i<=9; i++){if (i*s[1]%10==s[1]) dp[1][i*s[1]/10]++;}for (int i=2; i<=n; i++)for (int j=0; j<=9; j++)//枚举当前放置的数for (int k=0; k<=9; k++)//枚举上一位的进位if ((s[i]*j+k)%10==s[i]) dp[i][(s[i]*j+k)/10]=(dp[i][(s[i]*j+k)/10]+dp[i-1][k])%mod; ll ans=0;for (int i=0; i<=9; i++) ans=(ans+dp[n][i])%mod;printf("%lld\n",ans);return 0;}
如果觉得《CSUST 4002-你真的会字符串吗？（DP）》对你有帮助，请点赞、收藏，并留下你的观点哦！
