思路:数位dp,dp(i, j, k)表示考虑i位数,每位数可以任意取[0~9],并且这i位数的交错和为j,k=1表示前缀全是0(如000456),k=0表示前缀不为0。注意,前缀是否为0是这道题的一大坑点。在计算交错和的过程中可能会出现负数,这时应该加上一个数让它变成非负整数。f(123) = f(1) - f(23),根据这个来进行状态转移。
AC代码
#include <cstdio> #include <cmath> #include <cctype> #include <bitset> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<long long, long long> typedef long long LL; const int maxn = 400 + 5; const int Non = 200, mod = 1e9+7; LL dp[20][maxn][2], cnt[20][maxn][2]; int b[25]; int k; PI dfs(int pre, int d, int flag, int u, int pre_zero) { if(d == 0) { if(pre == k) return make_pair(0, 1); else return make_pair(0, 0); } int w = (k-pre)/u + Non; if(!flag && dp[d][w][pre_zero] != -1) return make_pair(dp[d][w][pre_zero], cnt[d][w][pre_zero]); int up = flag ? b[d] : 9; LL x = 0, y = 0; for(int i = 0; i <= up; ++i) { PI pi; if(pre_zero) { if(i == 0) pi = dfs(0, d-1, flag&(i==up), 1, 1); else pi = dfs(i, d-1, flag&(i==up), -1, 0); } else pi = dfs(pre + u*i, d-1, flag&(i==up), -u, 0); //用tmp防止溢出 LL tmp = pi.second * i % mod; tmp *= ((LL)pow(10, d-1))%mod; x += tmp + pi.first; x %= mod; y += pi.second; y %= mod; } if(!flag) { dp[d][w][pre_zero] = x; cnt[d][w][pre_zero] = y; } return make_pair(x, y); } int getBit(LL x) { int cur = 1; while(x) { b[cur++] = (int)(x%10); x /= 10; } return cur-1; } LL solve(LL x) { if(x <= 0) return 0; int n = getBit(x); PI ans = dfs(0, n, 1, 1, 1); return ans.first; } int main() { memset(dp, -1, sizeof(dp)); memset(cnt, 0, sizeof(cnt)); LL l, r; while(scanf("%lld%lld%d", &l, &r, &k) == 3) { LL a = solve(r), b = solve(l-1); printf("%lld\n", (a-b+mod)%mod); } return 0; }
如有不当之处欢迎指出!