西安城市建设职业学院官方网站,可以做围棋题的网站,郑州软件外包公司,莱芜网络推广公司平台文章目录题目描述解析题目描述 解析
迷惑。。。 首先#xff0c;比较容易想到用二进制状态压缩记录1-9是否在十进制中出现过 然后就是整除的问题 如果记录余数#xff0c;它的模数又有9个 开九维余数直接爆炸。。。 怎么办嘞#xff1f; 有一个结论#xff1a; 若#xf…
文章目录题目描述解析题目描述 解析
迷惑。。。 首先比较容易想到用二进制状态压缩记录1-9是否在十进制中出现过 然后就是整除的问题 如果记录余数它的模数又有9个 开九维余数直接爆炸。。。 怎么办嘞 有一个结论 若为p1、p2…pn的公倍数 那么(x%k)%pix%pi 因为k是p的质数所以这个结论还是挺显然的 那么本题就可以找到1-9的最小公倍数为2520 使它作为模数最后再进行判断即可 时间复杂度18位数*512状态压缩*2520取模结果*10每次dp枚举232243200 还是炸
怎么办 位数、状压、枚举基本没有优化的空间了 但我们注意到有些数无需记录取模结果依靠最后一位也能判断能否整除 首先可以想到5 但其实8也可以 怎么判断 设填到倒数第二位时数模4的结果为m 即 x4km 再填一位i后变成 40k10*mi 显然8能整除40k所以只需要判断10mi能否被8整除即可 这样公倍数那一维就不必考虑5和8降到了252 问题得到解决
#includebits/stdc.h
#define ll long long
using namespace std;
const int M 3000500;
const int N 200;
const int mod252;
int k;
ll l,r,dp[20][515][255];//dp[pos][op][res]
int a[20];
int n;
ll mi[19];
ll find(int pos,int op,int res,int lim,int add5,int add8){//for(int ipos;in;i) printf( );//printf(pos%d op%d res%d lim%d add5%d add8%d\n,pos,op,res,lim,add5,add8);if(pos0){int num0;numadd5op(1(4));numadd8op(1(7));for(int i1;i9;i){if(i5||i8) continue;if(op(1(i-1))res%i0) num;}//for(int ipos;in;i) printf( );//printf(num%d\n,num);ll ansnumk?1:0;return ans;}if(!limdp[pos][op][res]!-1) return dp[pos][op][res];ll ans0;int mx lim? a[pos] : 9;for(int i0;imx;i){int oopi?op|(1(i-1)):op;int aadd50,aadd80;if(pos1){if(i5||i0) aadd5;if(((res%4)*10i)%80) aadd8;}ansfind(pos-1,oop,(ll)(ires*10)%mod,limimx,aadd5,aadd8);//for(int jpos;jn;j) printf( );//printf((i%d ans%d)\n,i,ans);}if(!lim) dp[pos][op][res]ans;//for(int ipos;in;i) printf( );//printf(return %lld\n,ans);return ans;
}
//const int mod1e97;ll solve(ll x){n0;while(x){a[n]x%10;x/10;}return find(n,0,0,1,0,0);
}
int main() {mi[0]1;for(int i1;i18;i) mi[i]mi[i-1]*10;memset(dp,-1,sizeof(dp));// k2;
// int now0,pre0;
// for(int i1;i10500;i){
// nowsolve(i);
// if(nowpre1) printf(%d\n,i);
// prenow;
// }scanf(%d,k);//printf(k%d,k);scanf(%lld%lld,l,r);printf(%lld\n,solve(r)-solve(l-1));return 0;
}
/*
2 2 20
*/
