网站设计用户体验,京口区建设局网站,机构编制网站建设,济南上门做睫毛的网站正题
题目链接:http://pjudge.ac/problem/21652 题目大意
给出一个正整数kkk#xff0c;求第nnn个xxx满足x(10k−1)x\times (10^k-1)x(10k−1)中没有一个数位为999。 1≤n≤1018,1≤k≤181\leq n\leq 10^{18},1\leq k\leq 181≤n≤1018,1≤k≤18 解题思路
首先是从高位到低…正题
题目链接:http://pjudge.ac/problem/21652 题目大意
给出一个正整数kkk求第nnn个xxx满足x×(10k−1)x\times (10^k-1)x×(10k−1)中没有一个数位为999。
1≤n≤1018,1≤k≤181\leq n\leq 10^{18},1\leq k\leq 181≤n≤1018,1≤k≤18 解题思路
首先是从高位到低位逐步确定答案但是直接暴力算乘法肯定很麻烦我们考虑反过来做。
我们算第nnn个合法的x×(10k−1)x\times (10^k-1)x×(10k−1)然后再除以10k−110^k-110k−1。
那么现在问题就是给定一些确定的位求剩下的位有多少种不含999的组法能够拼出10k−110^k-110k−1的倍数。
然后一个数10k−110^k-110k−1的倍数的条件就是将它每kkk位分割一次提出来求和如果是10k−110^k-110k−1的倍数就合法。
段数不会太多我们可以暴力枚举10k−110^k-110k−1的倍数然后数位dp求解。
细节有点多。 code
#includecstdio
#includecstring
#includealgorithm
#includecctype
#define ll __int128
using namespace std;
const int W40;
int k,a[80],b[80];
ll n,f[80][10];
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void print(ll x)
{if(x9)print(x/10);putchar(x%100);return;}
ll solve(){int L(Wk-1)/k;ll pw1,ans0;for(int i1;ik;i)pwpw*(ll)10;pw--;for(int d1;dL;d){ll pd*pw;for(int i0;ik;i)b[i]p%10,p/10;memset(f,0,sizeof(f));f[0][0]1;for(int i0;ik;i){for(int z0;zL;z)for(int x(z0);x10;x)f[z/10][z%10]f[z][x],f[z][x]0;for(int j0;jL;j)for(int zL-1;z0;z--)for(int x9;x0;x--){if(!f[z][x])continue;ll rf[z][x];f[z][x]0;if(a[j*ki]-1)for(int y8;y0;y--)f[z(xy)/10][(xy)%10]r;else f[z(xa[j*ki])/10][(xa[j*ki])%10]r;}for(int z0;zL;z)for(int x0;x10;x)if(x!b[i])f[z][x]0;}for(int x0;x10;x)ansf[p][x];}return ans;
}
signed main()
{kread();nread();ll now0,las;int m(Wk-1)/k*k;for(int i0;im;i)a[i]-1;for(int im-1;i0;i--){a[i]0;now(lassolve());while(nown){a[i];now(lassolve());}now-las;}ll ans0;//print(now);for(int im-1,flag0;i0;i--)ansans*(ll)10a[i];ll pw1;for(int i0;ik;i)pwpw*(ll)10;pwpw-1;ans/pw;print(ans);return 0;
}
//1 8
