魔法数字
还是很麻烦的一道题……
题解
先证明一个结论：
若 (p=operatorname{lcm}(p_1,p_2,cdots,p_n)) ，则有(forall xin N ,iin[1,n], (xoperatorname{mod} p)operatorname{mod} p_i = xoperatorname{mod}p_i) .
证明：
因为(p=operatorname{lcm}(p_1,p_2,cdots,p_n))，则有(p = kcdot p_i).
则(x=scdot p+r = (kcdot s)p_i+r)
证毕。
应用：对于 (forall x) ，求 (xoperatorname{mod}{p_{1cdots n}}) ，可以求出 (x operatorname{mod} operatorname{lcm}(p)) ，再求其模。
对于此题：要求此数对于 (1cdots9) 的余数，可以求其与 (operatorname{lcm}(1cdots 9)) 的余数，再单独取余。
题目中还要求是否出现过某数，可以使用状压来解决。
则dp状态：
(dp(pos,st,lft)) 表示：
- 填到第 (pos) 位.
- 是否出现过某数的状态为 (st) .
- 取余后结果为 (lft) .
如果这样设计的话，空间复杂度是(O(18 imes 512 imes 2520) approx O(2e7)).
考虑如何优化这个过程：
如果末位是(0)或(5)，则它一定是(5)的倍数。
这样，就不需要考虑(5)的影响。其(operatorname{lcm})变为(504).
代码
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 1e5+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9'))ch=c,c=getchar();
while(c>='0'&&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
ll l,r;int k;
ll dp[20][520][510];
int num[20];
ll dfs(int pos,int st,int lft,short lst,bool lim){
// printf(" dfs(%d)
",pos);
if(!pos){
// printf(" ans add(%d,%d,%d,%d)
",st,lft,lst,lim);
int cnt = 0;
for(int i = 1 ; i <= 9 ; i ++)
if(i != 5 && st & (1<<(i-1)) && !(lft % i)) cnt ++;
if(st & (1<<4) && (lst == 5 || !lst)) cnt ++;
// puts(cnt >= k ? "YES" : "NO");
return cnt >= k;
}
if(~dp[pos][st][lft] && !lim) return dp[pos][st][lft];
int mx = lim ? num[pos] : 9;
ll ret = 0;
for(int i = 0 ; i <= mx ; i ++)
ret += dfs(pos-1,!i ? st : st | (1<<(i-1)) , (lft*10+i)%504 , i , lim && i==mx);
if(!lim) dp[pos][st][lft] = ret;
return ret;
}
inline ll solve(ll x){
// printf(" ans(%lld) = ",x);
int cnt = 0;
while(x)
num[++cnt] = x % 10,
x /= 10;
// printf("%lld
",dfs(cnt,0,0,0,1));
// puts("");puts("");;
return dfs(cnt,0,0,0,1);
}
signed main(){
memset(dp,-1,sizeof(dp));
k = read() , l = read() , r = read();
printf("%lld",solve(r)-solve(l-1));
return 0;
}