LightOJ1068(数位DP)

发现数位DP其实并不难调。。只要有数据的话。。。&＃xff08;当然考场需要对拍。。

这个要维护2个余数&＃xff0c;然后就是按照数位该有的模式转移即可&＃xff0c;不过k的范围非常大&＃xff0c;貌似会爆内存。。以前做数位dp其实根本就没想到会到内存不够用的地步丫。。仔细想想会发现&＃xff0c;数位和最多也才82&＃xff08;1999999999的情况&＃xff09;&＃xff0c;所以k>82直接输出0就可以了&＃xff0c;然后这样内存还是非常充裕的。。

#include
#include
#include
#include
#include
#include
#define inc(i,l,r) for(int i&＃61;l;i<&＃61;r;i&＃43;&＃43;)
#define dec(i,l,r) for(int i&＃61;l;i>&＃61;r;i--)
#define link(x) for(edge *j&＃61;h[x];j;j&＃61;j->next)
#define eps 1e-8
#define inf 1e9
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define succ(x) (1<#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define ls T[i<<1]
#define rs T[i<<1|1]
#define op T[i]
#define mid (x&＃43;y>>1)
#define NM 83
#define nm 100498
#define pi 3.141592653
using namespace std;
ll read(){ll x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(!isdigit(ch)){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(isdigit(ch))x&＃61;x*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return f*x;
}int _x,_y,k,n,b[NM],d[11][NM][NM];
bool V[11][NM][NM];
int dfs(int i,bool f,int t,int v){if(!i)return !t&&!v;if(!f&&V[i][t][v])return d[i][t][v];int m&＃61;f?b[i]:9,ans&＃61;0;inc(j,0,m)ans&＃43;&＃61;dfs(i-1,f&&j&＃61;&＃61;m,(t*10&＃43;j)%k,(v&＃43;j)%k);if(!f)d[i][t][v]&＃61;ans,V[i][t][v]&＃43;&＃43;;return ans;
}int solve(int x){n&＃61;0;for(int t&＃61;x;t;t/&＃61;10)b[&＃43;&＃43;n]&＃61;t%10;return dfs(n,1,0,0);
}int main(){int _&＃61;read();inc(T,1,_){_x&＃61;read();_y&＃61;read();k&＃61;read();if(k>82){printf("Case %d: 0\n",T);continue;}mem(V);mem(d);printf("Case %d: %d\n",T,solve(_y)-solve(_x-1));}return 0;
}


[Submit]   [Go Back]   [Status]