[luoguP3413] SAC#1 - 萌数（数位DP）

传送门

gtm的数位dp！

看到好多题解，都是记忆化搜索，好像非常方便啊，但是我还是用递推好了，毕竟还是有些类似数位dp的题用递推的思路，记忆化做不了，现在多培养一下思路

首先这道题，

只看长度大于等于2的回文串，那么只需要看aa和aba两种即可，再长的话肯定会包括这两种情况。

定义状态：f[i][j][k]表示长度为i，第i位是j，第i1位是k的不是回文数的个数

经过实践证明，直接求回文数个数好像真不是很好求。

然后各种细节的统计。

对于这种输入即为字符串的情况，我们可以先处理出一个半闭半开的区间的答案，再加上另一个数的贡献即可，而不需要先将R+1

#include <cstdio>#include <cstring>#include <iostream>#define N 1005#define p 1000000007#define LL long longusing namespace std;int n, d[N];string L, R;LL ans, f[N][10][10];inline void init()}inline LL calc(string s)sum++;ret = (ret + 10) % p;for(i = 2; i < n; i++)for(j = 1; j <= 9; j++)for(k = 0; k <= 9; k++)ret = (ret + f[i][j][k]) % p;for(i = n; i >= 2; i)if(ll == d[i] || l == d[i])ll = l, l = d[i];}if(flag) for(i = 0; i <= d[1]; i++)if(i != l && i != ll) ret = (ret + 1) % p;return (sum  ret) % p;}int main()printf("%lld\n", ans);return 0;}

上一篇：[luoguP3159] [CQOI2012]交换棋子（最小费用最大流）

下一篇：[BZOJ2393] Cirno的完美算数教室（dfs+容斥原理）