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

传送门

gtm的数位dp！

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

首先这道题，

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

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

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

然后各种细节的统计。

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

#include <cstdio>

#include <cstring>

#include <iostream>

#define N 1005

#define p 1000000007

#define LL long long

using namespace std;

int n, d[N];

string L, R;

LL ans, f[N][10][10];

inline void init()

{

	int i, j, k, l;

	for(i = 2; i <= 1000; i++)

		for(j = 0; j <= 9; j++)

			for(k = 0; k <= 9; k++) if(j != k)

			{

				for(l = 0; l <= 9; l++)

					if(l != k && l != j) f[i][j][k] += f[i - 1][k][l];

				if(i - 1 == 1) f[i][j][k]++;

				f[i][j][k] %= p;

			}

}

inline LL calc(string s)

{

	int i, j, k, flag = 1, l = -1, ll = -1;

	LL sum = 0, ret = 0;

	n = s.length();

	if(n == 1) return 0;

	memset(d, 0, sizeof(d));

	for(i = n; i >= 1; i--)

	{

		d[i] = s[n - i] - '0';

		sum = (sum * 10 + d[i]) % p;

	}

	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--)

	{

		for(j = 0; j < d[i]; j++) if(!(i == n && !j))

			for(k = 0; k <= 9; k++)

			{

				if(ll == j || l == j || l == k || j == k) continue;

				ret = (ret + f[i][j][k]) % p;

			}

		if(ll == d[i] || l == d[i])

		{

			flag = 0;

			break;

		}

		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()

{

	int i;

	init();

	cin >> L >> R;

	ans = (calc(R) - calc(L) + p) % p;

	for(i = 1; i < L.length(); i++)

		if(L[i] == L[i - 1] || (i >= 2 && L[i] == L[i - 2]))

		{

			ans = (ans + 1) % p;

			break;

		}

	printf("%lld\n", ans);

	return 0;

}

巴特西

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

最新文章

热门文章