和山东省选的储能表很像，都是带上限的数位dp，先差分一下，然后询问两次即可。这里要注意10^10如果减1就变成10位数了，所以这里是加1。 用f[i][j][a][b][c][d][e]来表示。。。 做到第i位，上一位是j（第0位就用10表示），a表示最后两位是否一样，b表示是否已经出现连续三个数相等，c表示是否有4，d表示是否有8，e表示是否小于上限。
#include<cmath>#include<cstdio>#include<vector>#include <queue>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 100000#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;ll f[20][15][2][2][2][2][2],l,r;int p[20];ll calc(ll q){ ll num,t,i,j,k,a,b,c,d,e,x,y,z,m,n,res; memset(f,0,sizeof(f)); num = 0; t = q; while (t) {p[++num]=t%10; t/=10;} fo(i,1,num/2) swap(p[i],p[num-i+1]); f[0][10][0][0][0][0][1] = 1; //初始化 fo(i,0,num-1) fo(j,0,10) fo(a,0,1) fo(b,0,1) fo(c,0,1) fo(d,0,1) fo(e,0,1) if (f[i][j][a][b][c][d][e]) fo(k,0,9) { if ((k > p[i+1]) && e) continue; //大于上限 x = (k == j); //最后两位是否一样 y = b?b:(a+x)==2; //是否连续三个数相等 z = c?c:(k==4); m = d?d:(k==8); if (z + m == 2) continue; //不能同时存在4和8 n = ((k == p[i+1] && e))?1:0; f[i+1][k][x][y][z][m][n] += f[i][j][a][b][c][d][e]; } res = 0; fo(j,0,9) fo(a,0,1) fo(c,0,1) for (d = 0;(d<=1)&&(d+c<2); d++) res += f[num][j][a][1][c][d][0]; return res;}int main(){ scanf("%lld%lld",&l,&r); PRintf("%lld/n",calc(r+1)-calc(l)); //注意l=10^10时 l-1不是11位数 return 0;}新闻热点
疑难解答
