bzoj2757【scoi2012】Blinker的仰慕者

题目描述

Blinker 有非常多的仰慕者，他给每个仰慕者一个正整数编号。而且这些编号还隐藏着特殊的意义，即编号的各位数字之积表示这名仰慕者对Blinker的重要度。现在Blinker想知道编号介于某两个值A,B之间，且重要度为某个定值K的仰慕者编号和。

输入格式

输入的第一行是一个整数N，表示Blinker想知道的信息个数。
接下来的N行，每行有三个数，A,B,K。表示 Blinker想知道编号介于A和B之间的，
重要度为K的仰慕者的编号和。

输出格式

输出N行，每行输出介于A和B之间，重要度为 K的仰慕者编号和。结果可能很大，
模上20120427。

提示

【数据范围】
对于20%的数据，保证： 2<=A<=B<=1000000000，1<=N<=30
对于50%的数据，保证：2<=A<=B<=1000000000000000000，1<=N<=30
对于100%的数据，保证： 2<=A<=B<=1000000000000000000，1<=N<=5000

题解：
- 由于因子只有2 3 5 7 , 状态大概有3e4+，不超过4e4;
- 用HASH_TABLE存下来；
- 多组询问，先预处理$i$位的答案；
- 对每组询问$dfs$统计答案，如果没有前导零并且没有抵达上界则直接返回，否则进一步$dfs$
- 代码不太好些，注释里有关于变量的说明；
- 注意$K=0$和$K \neq 0$最好分开统计；
- $n$为位数上界,时间复杂度：$O(T*10n +n*4e4*10)$

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 const int N=,M=4e4,sz=,mod=;

 ll A,B,K;

 int cnt,a[N],pw[N];

 int o,hd[sz],nt[sz];ll v[sz];

 void upd(int&x,int y){x+=y;if(x>=mod)x-=mod;}

 void add(ll x){

     int u=x%sz;

     for(int i=hd[u];i;i=nt[i])if(v[i]==x)return;

     nt[++o]=hd[u],hd[u]=o,v[o]=x;

 }

 int find(ll x){

     int u=x%sz;

     for(int i=hd[u];i;i=nt[i])if(v[i]==x)return i;

     return ;

 }//HASH表

 void dfs(int x,int y,ll z){

     if(x==)add(z);

     else{

         if(!y)return;

         for(int i=x;i<=;++i){

             dfs(i,y-,z);

             z*=y;

         }

     }

 }//dfs方案

 namespace Solve{

     int f[N][M],g[N][M];//f[位数][乘积]

     void init(){

         f[][]=;

         for(int i=;i<;++i)

         for(int j=;j<=o;++j)

         if(f[i][j]){

             for(int l=;l<=;++l){

                 int y=find(v[j]*l);

                 upd(f[i+][y],f[i][j]);

                 upd(g[i+][y],(g[i][j]*+f[i][j]*l)%mod);

             }

         }

     }//预处理i位无限制的答案

     int cal1(int i,int j,int k,ll x,ll y){//已经枚举好的位数，前导零，上界，前i位的值，当前K

         if(i==cnt)return y==?x:;

         if(!k&&!j)return (1ll*x*pw[cnt-i]%mod*f[cnt-i][find(y)]%mod+g[cnt-i][find(y)])%mod;

         int re=,l=j?:,r=k?a[i+]:;

         for(int i1=l,t;i1<=r;++i1)if(!i1||y%i1==){

             ll y1=!i1?y:y/i1;

             upd(re, t=cal1(i+,j&&!i1,k&&i1==a[i+],(x*+i1)%mod,y1));

         }

         return re;

     }

     int cal0(int i,int j,int k,ll x,ll y){//前四个同cal1，y为前i为是否出现0

         if(i==cnt)return !y?x:;

         if(!k&&!j){

             if(!y)return (1ll*x*pw[cnt-i]%mod*pw[cnt-i]%mod+1ll*(pw[cnt-i]-)*pw[cnt-i]/%mod)%mod;//后面cnt-i任意；

             else return 1ll*x*pw[cnt-i]%mod*f[cnt-i][o]%mod+g[cnt-i][o];//后面cnt-i为乘积为0；

         }

         int re=,l=,r=k?a[i+]:;

         for(int i1=l;i1<=r;++i1){

             int y1=j&&!i1?:y*i1;

             upd(re, cal0(i+,j&&!i1,k&&i1==a[i+],(x*+i1)%mod,y1));

         }

         return re;

     }

     //注意理解一下两个方面：

     //是如何统计前i位达到上界，i+1位不是上界的答案的；(状态k)

     //是如何统计位数小于上界位数cnt的答案的; (状态j)

     //上界是如何被统计的(line44)

 }

 int main(){

     #ifndef ONLINE_JUDGE

     freopen("T2.in","r",stdin);

     freopen("T2.out","w",stdout);

     #endif

     dfs(,,);add();

     Solve::init();

     for(int i=pw[]=;i<=;++i)pw[i]=pw[i-]*%mod;

     int T;scanf("%d",&T);

     while(T--){

         int ans=;

         scanf("%lld%lld%lld",&A,&B,&K);A--;

         cnt=;while(A)a[++cnt]=A%,A/=;

         for(int i=;i<=cnt>>;++i)swap(a[i],a[cnt-i+]);

         ans-= K?Solve::cal1(,,,,K) : Solve::cal0(,,,,);

         cnt=;while(B)a[++cnt]=B%,B/=;

         for(int i=;i<=cnt>>;++i)swap(a[i],a[cnt-i+]);

         ans+= K?Solve::cal1(,,,,K) : Solve::cal0(,,,,);

         printf("%d\n",(ans%mod+mod)%mod);

     }

     return ;

 }

仰慕者

bzoj2757【scoi2012】Blinker的仰慕者

题目描述

输入格式

输出格式

提示

题解：