{题解}[jzoj4799]【NOIP2016提高A组模拟9.24】我的快乐时代

Description

也就是说

Analysis

因为x最多只有6位 所以有多种方法水过 暴力的，考虑枚举其中对应的两位(即第 i 位与第k−i−1位) 单独考虑他们对答案的贡献 通过简单的数位DP计算合法的数字个数

Code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const long long Mo = 1000000007; long long sw[100],bz[100],f[100][4]; long long L,R; long long DP(long long x) { memset(f,0,sizeof f); f[0][2] = 1; for (long long i = 1;i <= x;i ++) { long long xhm = 0; if(i == x) xhm = 1; for (long long j = xhm;j <= 9;j ++) { if (bz[i] == -1 || bz[i] == j) { if (j > sw[i]) { f[i][3] = (f[i][3] + f[i - 1][1] + f[i - 1][2] + f[i-1][3]) % Mo; } else if (j == sw[i]) { f[i][1] = (f[i][1] + f[i - 1][1]) % Mo; f[i][2] = (f[i][2] + f[i - 1][2]) % Mo; f[i][3] = (f[i][3] + f[i - 1][3]) % Mo; } else { f[i][1] = (f[i][1] + f[i - 1][1] + f[i - 1][2] +f[i - 1][3]) % Mo; } } } } if (x < sw[0]) return (f[x][1] + f[x][2] + f[x][3]) % Mo; else return (f[x][1] + f[x][2]) % Mo; } long long Ans(long long X) { long long Re = 0; long long x = X; sw[0] = 0; while ( x ) { sw[++ sw[0]] = x % 10; x /= 10; } memset(bz, 255, sizeof bz); for (long long i = 1;i <= sw[0];i ++) { for (long long j = i;j <= sw[0];j ++) { if (i + j - 1 <= sw[0]) { if (i == j) { for (long long x = 1;x <= 9;x ++) { bz[i] = x; Re = (Re + DP(i * 2 - 1) % Mo * (x * x) % Mo) % Mo; bz[i] = -1; } } else { for (long long x = 1;x <= 9;x ++) { for(long long y = 1;y <= 9;y ++) { bz[i] = x,bz[j] = y; Re = (Re + DP(i + j - 1) % Mo * (x * y * 2) % Mo) % Mo; bz[i] = -1,bz[j] = -1; } } } } } } return Re % Mo; } int main() { scanf("%lld%lld", &L, &R); long long ans = 0; ans = (Ans(R) % Mo - Ans(L - 1) % Mo + Mo) % Mo; printf("%lld", ans); }