Beautiful numbers

//https://www.cnblogs.com/xcw0754/p/4854539.html
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=2520;
int p[49]={0,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,
180,210,252,280,315,360,420,504,630,840,1260,2520},has[2521],T,a[23],i;
ll l,r,f[23][49][M];
int LCM(int x,int y){
    return x/__gcd(x,y)*y;
}
ll dfs(int len,int lcm,int le,int fl){
    if (!len) return lcm && le%p[lcm]==0;
    if (!fl && ~f[len][lcm][le]) return f[len][lcm][le];
    int up=fl?a[len]:9;
    ll res=0;
    for (int i=0;i<=up;i++){
        int t=lcm?has[LCM(p[lcm],max(i,1))]:i;
        res+=dfs(len-1,t,(le*10+i)%M,fl && i==up);
    }
    if (!fl) f[len][lcm][le]=res;
    return res;
}
ll calc(ll x){
    int len=0;
    while (x){
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1);
}
int main(){
    memset(f,-1,sizeof(f));
    scanf("%d",&T);
    for (i=0;i<49;i++) has[p[i]]=i;
    while (T--){
        scanf("%I64d%I64d",&l,&r);
        printf("%I64d\n",calc(r)-calc(l-1));
    }
}

HDU2089 不要62

//https://www.cnblogs.com/wenruo/p/4725005.html
#include<bits/stdc++.h>
using namespace std;
int f[9][10],l,r,i,j,k,d[13];
int calc(int x){
    int len=0;
    while (x){
        d[++len]=x%10;
        x/=10;
    }
    int ans=0;
    d[len+1]=0;
    for (int i=len;i;i--){
        for (int j=0;j<d[i];j++)
            if (j!=2 || d[i+1]!=6) ans+=f[i][j];
        if (d[i]==4 || d[i]==2 && d[i+1]==6) break;
    }
    return ans;
}
int main(){
    f[0][0]=1;
    for (i=1;i<=7;i++)
        for (j=0;j<=9;j++)
            for (k=0;k<=9;k++)
                if (j!=4 && !(j==6 && k==2)) f[i][j]+=f[i-1][k];
    while (1){
        scanf("%d%d",&l,&r);
        if (!l && !r) return 0;
        printf("%d\n",calc(r+1)-calc(l));
    }
}

HDU 4734 F(x)

#include<bits/stdc++.h>
using namespace std;
int d[13],f[13][9302],a,b,T,Case;
int dfs(int pos,int st,int fl){
    if (!pos) return st>=0;
    if (st<0) return 0;
    if (!fl && f[pos][st]!=-1) return f[pos][st];
    int up=fl?d[pos]:9,ans=0;
    for (int i=0;i<=up;i++) ans+=dfs(pos-1,st-(i<<(pos-1)),fl&&(i==up));
    if (!fl) f[pos][st]=ans;
    return ans;
}
int F(int x){
    int s=0,i=0;
    while (x) s+=x%10<<(i++),x/=10;
    return s;
}
int get(int a,int b){
    int len=0;
    while (b){
        d[++len]=b%10;
        b/=10;
    }
    return dfs(len,F(a),1);
}
int main(){
    memset(f,-1,sizeof(f));
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&a,&b);
        printf("Case #%d: %d\n",++Case,get(a,b));
    }
}

POJ 3252 Round Numbers

//https://blog.csdn.net/lyy289065406/article/details/6648458
#include<cstdio>
using namespace std;
int i,j,c[33][33],l,r,d[35];
int solve(int x){
    int len=0,sum=0,zero=0;
    while (x) d[++len]=x&1,x>>=1;
    for (int i=1;i<len-1;i++)
        for (int j=i/2+1;j<=i;j++) sum+=c[i][j];
    for (int i=len-1;i;i--)
        if (d[i])
            for (int j=(len+1)/2-zero-1;j<i;j++) sum+=c[i-1][j];
        else zero++;
    return sum;
}
int main(){
    for (i=0;i<32;i++)
        for (j=0;j<=i;j++)
            if (!j || i==j) c[i][j]=1;
            else c[i][j]=c[i-1][j-1]+c[i-1][j];
    scanf("%d%d",&l,&r);
    printf("%d",solve(r+1)-solve(l));
}

HDU3709 balanced Number

//https://blog.csdn.net/dgq8211/article/details/9302069
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[20][20][1801],l,r;
int T,d[20];
ll dfs(int len,int cent,int sum,int fl){
    if (!len) return sum==0;
    if (sum<0) return 0;
    if (!fl && f[len][cent][sum]!=-1) return f[len][cent][sum];
    int up=fl?d[len]:9;
    ll ans=0;
    for (int i=0;i<=up;i++) ans+=dfs(len-1,cent,sum+i*(len-cent),fl&&(i==up));
    if (!fl) f[len][cent][sum]=ans;
    return ans;
}
ll get(ll x){
    if (x<0) return 0;
    int len=0;
    while (x) d[++len]=x%10,x/=10;
    ll ans=0;
    for (int i=len;i;i--) ans+=dfs(len,i,0,1);
    return ans-len+1;
}
int main(){
    memset(f,-1,sizeof(f));
    scanf("%d",&T);
    while (T--){
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",get(r)-get(l-1));
    }
}

UVA1350 Pinary

#include<cstdio>
using namespace std;
long long f[40];
int T,x,i;
int main(){
    f[0]=f[1]=1;
    for (i=2;i<40;i++) f[i]=f[i-1]+f[i-2];
    scanf("%d",&T);
    while (T--){
        scanf("%d",&x);
        for (i=39;x<f[i];i--);
        for (;i;i--)
            if (x>=f[i]) putchar('1'),x-=f[i];
            else putchar('0');
        putchar('\n');
    }
}

ural1057 Amount of Degrees

//http://blog.sina.com.cn/s/blog_9aa2786a0101a5w3.html
#include<cstdio>
using namespace std;
typedef long long ll;
int x,y,k,b,n,i,j;
ll t[33],c[33][33];
ll calc(int x){
    if (x<=0) return 0;
    int len=0,b[33];
    for (int i=n;i>=0;i--)
        if (x>=t[i]) x-=t[i],b[++len]=i;
    ll ans=0;
    for (int i=1;i<=len && i<=k;i++) ans+=c[b[i]][k-i+1];
    if (len>=k) ans++;
    return ans;

}
int main(){
    scanf("%d%d%d%d",&x,&y,&k,&b);
    t[0]=1;
    while (t[n]<y) n++,t[n]=t[n-1]*b;
    for (i=0;i<=n;i++)
        for (j=0;j<=i;j++)
            if (!j || i==j) c[i][j]=1;
            else c[i][j]=c[i-1][j]+c[i-1][j-1];
    printf("%lld",calc(y)-calc(x-1));
}

HDU4352 XHXJ’s Lis

//https://www.cnblogs.com/silver-bullet/p/3259205.html
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[20][10][1024][11],l,r;
int i,j,T,k,ha[1024],ne[1024][10],d[20];
int go(int st,int num){
    int pos=-1;
    for (int i=num;i<10;i++)
        if (st&(1<<i)){
            pos=i;
            break;
        }
    if (pos!=-1) st^=1<<pos;
    st|=1<<num;
    return st;
}
ll dfs(int len,int num,int st,bool zero,bool fl){
    if (!len) return ha[st]==k;
    if (!fl && f[len][num][st][k]!=-1) return f[len][num][st][k];
    ll ans=0;
    int up=fl?d[len]:9;
    for (int i=0;i<=up;i++)
        if (zero && !i) ans+=dfs(len-1,0,0,1,fl && i==up);
        else ans+=dfs(len-1,i,ne[st][i],0,fl && i==up);
    if (!fl) f[len][num][st][k]=ans;
    return ans;
}
ll cal(ll x){
    int len=0;
    while (x){
        d[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1,1);
}
int main(){
    memset(f,-1,sizeof(f));
    for (i=0;i<1<<10;i++)
        for (j=0;j<10;j++){
            if (i&(1<<j)) ha[i]++;
            ne[i][j]=go(i,j);
        }
    scanf("%d",&T);
    for (i=1;i<=T;i++){
        scanf("%lld%lld%d",&l,&r,&k);
        printf("Case #%d: %lld\n",i,cal(r)-cal(l-1));
    }
}

HDU3652 B-number

#include<cstdio>
#include<cstring>
using namespace std;
int f[12][14][3],n,d[12];
int dfs(int len,int mod,int st,bool fl){
    if (!len) return mod==0 && st==2;
    if (!fl && f[len][mod][st]!=-1) return f[len][mod][st];
    int up=fl?d[len]:9,ans=0;
    for (int i=0;i<=up;i++){
        int mod1=(mod*10+i)%13,st1=st;
        if (!st && i==1) st1=1;
        if (st==1 && i!=1) st1=0;
        if (st==1 && i==3) st1=2;
        ans+=dfs(len-1,mod1,st1,fl&&(i==up));
    }
    if (!fl) f[len][mod][st]=ans;
    return ans;
}
int cal(int x){
    int len=0;
    while (x) d[++len]=x%10,x/=10;
    return dfs(len,0,0,1);
}
int main(){
    memset(f,-1,sizeof(f));
    while (~scanf("%d",&n)) printf("%d\n",cal(n));
}

ZOJ3494 BCD Code

//https://www.cnblogs.com/czllgzmzl/p/5221802.html
#include<cstdio>
#include<cstring>
using namespace std;
const int M=1e9+9,N=2003;
int fail[N],q[N],ch[N][2],f[N][203],tot,u[N][203],T,len,n,i,ans,num[N][10];
bool gg[N];
char s[203];
void insert(int len){
    int now=0;
    for (int i=0;i<len;i++){
        int c=s[i]^48;
        if (!ch[now][c]) ch[now][c]=++tot;
        now=ch[now][c];
    }
    gg[now]=1;
}
void build(){
    int h=0,t=1,tmp,now;
    while (h<t){
        now=q[++h];
        for (int i=0;i<2;i++)
            if (ch[now][i]){
                for (tmp=fail[now];tmp && !ch[tmp][i];tmp=fail[tmp]);
                fail[ch[now][i]]=now?ch[tmp][i]:0;
                gg[ch[now][i]]|=gg[fail[ch[now][i]]]|gg[now];
                q[++t]=ch[now][i];
            }else{
                for (tmp=fail[now];tmp && !ch[tmp][i];tmp=fail[tmp]);
                ch[now][i]=ch[tmp][i];
            }
    }
    for (int i=0;i<=tot;i++)
        for (int j=0;j<2;j++)
            if (gg[ch[i][j]] || gg[i]) ch[i][j]=-1;
    for (int i=0;i<=tot;i++)
        if (!gg[i])
            for (int j=0;j<=9;j++){
                now=i;
                for (int k=8;k && now!=-1;k>>=1) now=ch[now][(k&j)!=0];
                num[i][j]=now;
            }
    for (int i=0;i<=tot;i++)
        if (!gg[i]) f[i][0]=1,u[i][0]=T;
}
int dfs(int x,int step){
    if (u[x][step]==T) return f[x][step];
    int ans=0;
    for (int i=0;i<=9;i++)
        if (num[x][i]!=-1) ans+=dfs(num[x][i],step-1),ans-=ans>=M?M:0;
    u[x][step]=T;
    return f[x][step]=ans;
}
int get(int len){
    for (int i=0;i<len;i++) s[i]^=48;
    int ans=0;
    for (int i=1;i<len;i++)
        for (int j=1;j<=9;j++)
            if (num[0][j]!=-1) ans+=dfs(num[0][j],i-1),ans-=ans>=M?M:0;
    for (int i=1;i<s[0];i++)
        if (num[0][i]!=-1) ans+=dfs(num[0][i],len-1),ans-=ans>=M?M:0;
    int now=num[0][s[0]];
    for (int i=1;i<len && now!=-1;i++){
        for (int j=0;j<s[i];j++)
            if (num[now][j]!=-1) ans+=dfs(num[now][j],len-i-1),ans-=ans>=M?M:0;
        now=num[now][s[i]];
    }
    return ans;
}
void add(){
    int i,j;
    for (i=len-1;i>=0;i--)
        if (s[i]!='9') break;
    if (i>=0)
        for (s[i]++,j=i+1;j<len;j++) s[j]='0';
    else{
        len++;
        for (s[0]='1',j=1;j<len;j++) s[j]='0';
    }
}
int main(){
    for (scanf("%d",&T);T;T--){
        scanf("%d",&n);
        memset(gg,0,tot+1);
        memset(ch,0,(tot+1)<<3);
        tot=0;
        for (i=1;i<=n;i++) scanf("%s",s),insert(strlen(s));
        build();
        scanf("%s",s);len=strlen(s);ans=-get(len);
        scanf("%s",s);len=strlen(s);add();ans+=get(len);
        if (ans<0) ans+=M;
        printf("%d\n",ans);
    }
}

恨7不成妻

//https://blog.csdn.net/to_be_better/article/details/50727559
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e9+7;
struct node{
    ll cnt,sum,sqr;
    node(){}
    node(ll a,ll b,ll c):cnt(a),sum(b),sqr(c){}
}dp[20][7][7];
ll c[20],l,r;
int T,d[20],i;
node dfs(int len,int mod1,int mod2,bool fl){
    if (len<0) return node(mod1 && mod2,0,0);
    if (!fl && dp[len][mod1][mod2].cnt!=-1) return dp[len][mod1][mod2];
    int up=fl?d[len]:9;
    node ans=node(0,0,0);
    for (int i=0;i<=up;i++)
        if (i!=7){
            node t=dfs(len-1,(mod1+i)%7,(mod2*10+i)%7,fl&&(i==up));
            ans.cnt=(ans.cnt+t.cnt)%M;
            ans.sum=(ans.sum+(i*c[len]%M*t.cnt%M+t.sum)%M)%M;
            ans.sqr=(ans.sqr+(i*c[len]*i%M*c[len]%M*t.cnt%M+2*i*c[len]%M*t.sum%M+t.sqr)%M)%M;
        }
    if (!fl) dp[len][mod1][mod2]=ans;
    return ans;
}
ll get(ll x){
    int len=0;
    while (x) d[len++]=x%10,x/=10;
    return dfs(len-1,0,0,1).sqr;
}
int main(){
    scanf("%d",&T);
    c[0]=1;
    for (i=1;i<20;i++) c[i]=c[i-1]*10%M;
    memset(dp,-1,sizeof(dp));
    while (T--){
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",(get(r)-get(l-1)+M)%M);
    }
}

数字计数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    ll a[10];
    friend node operator +(node x,node y){
        for (int i=0;i<=9;i++) x.a[i]+=y.a[i];
        return x;
    }
}a,b,f[15][10];
ll t[15],l,r;
int i,j,k;
node calc(ll x){
    node ans;
    for (int i=1;i<=9;i++) ans.a[i]=0;
    ans.a[0]=1;
    if (!x) return ans;
    int len=14;
    while (t[len]>x) len--;
    for (int i=1;i<len;i++)
        for (int j=1;j<=9;j++) ans=ans+f[i][j];
    int cur=x/t[len];
    for (int i=1;i<cur;i++) ans=ans+f[len][i];
    x%=t[len--];
    ans.a[cur]+=x+1;
    while (len){
        cur=x/t[len];
        for (int i=0;i<cur;i++) ans=ans+f[len][i];
        x%=t[len--];
        ans.a[cur]+=x+1;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&l,&r);
    t[1]=1;
    for (i=2;i<15;i++) t[i]=t[i-1]*10;
    for (i=0;i<=9;i++) f[1][i].a[i]=1;
    for (i=2;i<15;i++)
        for (j=0;j<=9;j++)
            for (k=0;k<=9;k++){
                f[i][k]=f[i][k]+f[i-1][j];
                f[i][k].a[k]+=t[i-1];
            }
    a=calc(r);b=calc(l-1);
    for (i=0;i<=9;i++) printf("%lld%c",a.a[i]-b.a[i],i==9?'\n':' ');
}

数字之积

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
ll a[6003],n,l,r,dp[20][6003];
int tot,p[4]={2,3,5,7},d[20],i,j,k;
void init(ll now,ll pre){
    for (int i=pre;i<4;i++){
        if (now*p[i]>n) break;
        mp[now*p[i]]=++tot;
        a[tot]=now*p[i];
        init(now*p[i],i);
    }
}
ll get(ll x){
    if (!x) return 0;
    ll ans=0;int len=0;
    while (x) d[++len]=x%10,x/=10;
    for (int i=1;i<len;i++)
        for (int j=1;j<=tot;j++)
            if (a[j]<=n) ans+=dp[i][j];
    ll pre=1;
    for (int i=len;i>=2;i--){
        for (int k=1;k<d[i];k++)
            for (int j=1;j<=tot;j++)
                if (pre*k*a[j]<=n) ans+=dp[i-1][j];
        pre*=d[i];
        if (!pre || pre>n) break;
    }
    for (int i=1;i<=d[1];i++)
        if (pre*i && pre*i<=n) ans++;
    return ans;
}
int main(){
    scanf("%lld",&n);
    mp[1]=++tot;a[1]=1;
    init(1,0);
    for (i=1;i<=9;i++) dp[1][mp[i]]=1;
    for (i=1;i<=17;i++)
        for (j=1;j<=tot;j++)
            for (k=1;k<=9;k++) dp[i+1][mp[a[j]*k]]+=dp[i][j];
    scanf("%lld%lld",&l,&r);
    printf("%lld",get(r-1)-get(l-1));
}