[数位dp] upcoj 2223 A

题意：

A数列为，包含7或者能被7整除的数从小到大构成。

{a[1]=7,a[2]=14,a[3]=17,a[4]=21,a[5]=27,a[6]=28,a[7]=35,a[8]=37,a[9]=42,a[10]=47};

B数列为，是A数列里的数，但不包含第a[i]个A数列里的数列。

也就是B数列要去掉 a[7],a[14],a[17]这些要去掉。

{b[1]=7,b[2]=14,b[3]=17,b[4]=21,b[5]=27,b[6]=28,b[7]=37,b[8]=42,b[9]=47,b[10]=49};

现在给N，求第N个B数列里的数。

思路：

首先值得肯定的是，，我们必须知道A数列，所以数位dp关于A数列。这个都很简单。

dp[i][j][k] 第i位，余数是j，k 代表是否含有了7.

然后就看第N个B数列的数，实际是第几个A数列的数。

我们假设是第N个B 数列的数，是第X个A数列的数。

那么满足N=X-solve(X) solve(X) 代表1~X中有几个A数列的数。

会发现X-solve(X) 随着X的增大而增大。

所以二分出最小满足X-solve(X)=N 的X。

接着再一个二分求第X个A数列的数是多少就可以了~

最后就是需要注意，题目要求范围是2^63-1，所以开成 unsigned long long。

代码：

#include"stdio.h"#include"algorithm"#include"string.h"#include"map"#include"iostream"#include"queue"#include"string"#define ll unsigned long longusing namespace std;ll dp[22][8][2];int num[22];ll dfs(int site,int s,int o,int f){if(site==0){if(o==1) return 1;if(s==0) return 1;return 0;}if(!f && dp[site][s][o]!=-1) return dp[site][s][o];ll ans=0;int len=f?num[site]:9;for(int i=0; i<=len; i++){if(o==1) ans+=dfs(site-1,(s*10+i)%7,1,f&&i==len);else{if(i==7) ans+=dfs(site-1,(s*10+i)%7,1,f&&i==len);else ans+=dfs(site-1,(s*10+i)%7,0,f&&i==len);}}if(!f) dp[site][s][o]=ans;return ans;}ll solve(ll x){int cnt=0;while(x){num[++cnt]=x%10;x/=10;}return dfs(cnt,0,0,1)-1;}int main(){ll n;memset(dp,-1,sizeof(dp));while(scanf("%llu",&n)!=-1){ll l=1,r=(1LL<<63)-1,mid,kx;while(l<=r){mid=(l+r)/2;ll tep=mid-solve(mid);if(tep>=n){kx=mid;r=mid-1;}else l=mid+1;}ll ans;l=1,r=(1LL<<63)-1;while(l<=r){mid=(l+r)/2;if(solve(mid)>=kx){ans=mid;r=mid-1;}else l=mid+1;}printf("%llu\n",ans);}return 0;}

伟人之所以伟大，是因为他与别人共处逆境时，