精华内容
下载资源
问答
  • hdu4507

    2013-09-30 13:08:00
    数位dp,终于守得云开见月明了。建议初学者先试试两道比较简单的hdu2089,hdu3555。 ...  数位dp也是一种基于状态压缩、优化的动态规划。不同的是,它的压缩和优化往往基于数的一些特性。... 这种d...

      数位dp,终于守得云开见月明了。建议初学者先试试两道比较简单的hdu2089,hdu3555

      鸣谢:http://blog.csdn.net/acm_cxlove/article/details/8707084。

      数位dp也是一种基于状态压缩、优化的动态规划。不同的是,它的压缩和优化往往基于数的一些特性。而数最基本的表现形式:a/b --- [a/b]、[a%b]。

      这种dp才是体现一个人智慧的地方。(额外想为ACM竞赛的同学说两句,个人还是特别顶复旦出题的,至少它出的绝大部分题目都是可以自己通过大学以前的数学知识慢慢想到,而不是像某些学校的题目,只要听说过、学过、看过,某一个不知道哪里冒出来的数学理论就能瞬间AC,否则***。还是不放水了,言归正传)

      本题,中文描述的,不解释了。初学者往往都会往容斥的方面想,(也不是不可以)但其实条件2、条件3的综合比较困难了,代码量和复杂度可能都会很大。

      所以直接递归找跟7有关的数比较科学,假设原数字a+b位,如果搜索前a位fa(fa后b位都是0),后面b位跟7有关的任何一个数x,产生的结果和是(fa+x)^2+x^2。对所有的x,就有{fa^2*cnt(x)+2fa*sum(x)+sum(x^2)=f(a+b,b)}+f(b,0)。这个很容易想到,那么如果搜索时刚好按a从小到大拆分呢?不就是很明显了吗?

     1 #include <iostream>
     2 #include <cstring>
     3 #include <cstdio>
     4 #include <algorithm>
     5 using namespace std;
     6 #define LL long long
     7 const LL mod = 1000000007LL;
     8 #define mp(a,b) make_pair(a,b)
     9 int bit[21];
    10 //长度,是否有7,数字和%7,数字%; 数字和、结果和、数字个数
    11 long long s1[20][2][7][7],s2[20][2][7][7],cnt[20][2][7][7];
    12 LL fac[20]={1};
    13 typedef pair<pair<LL,LL>,LL> pll;
    14 pll DP(int len,int a,int b,int c,int g){
    15     //printf("len = %d, %d, %d, %d, g = %d\n",len,a,b,c,g);
    16     if(g && cnt[len][a][b][c] >= 0)
    17         return mp(mp(cnt[len][a][b][c],s1[len][a][b][c]),s2[len][a][b][c]);
    18     if(len <= 0){
    19         if(b&&c&&!a) cnt[0][a][b][c]=0;
    20         else cnt[0][a][b][c]=1;
    21         s1[0][a][b][c]=s2[0][a][b][c]=0;
    22         return mp(mp(cnt[len][a][b][c],s1[len][a][b][c]),s2[len][a][b][c]);
    23     }
    24     int bound=bit[len]; if(g) bound=9;
    25     LL tcnt=0,ts1=0,ts2=0;
    26     int nl=len-1,na,nb,nc;
    27     for(int i=0;i<=bound;i++){
    28         na=(a||i==7); nb=(b+i)%7; nc=(c*10+i)%7;
    29         pll p=DP(nl,na,nb,nc,g||(i<bound));
    30         LL f = fac[nl]*i % mod; //f按位拆分,不用靠递归记录!!!
    31         tcnt= (tcnt+p.first.first)%mod;
    32         ts1 = (ts1+p.first.second+p.first.first*f)%mod;
    33         ts2 = (ts2+p.first.first*(f*f%mod)%mod+p.first.second*f*2%mod+p.second)%mod;
    34     }
    35     if(g){
    36         cnt[len][a][b][c] = tcnt;
    37         s1[len][a][b][c] = ts1;
    38         s2[len][a][b][c] = ts2;
    39     }
    40     return mp(mp(tcnt,ts1),ts2);
    41 }
    42 LL sum(LL n){
    43     LL a=n,b=n+1,c=2*n+1;
    44     LL x=3,y=2;
    45     if(a%x==0) a/=x,x=1;if(a%y==0) a/=y,y=1;
    46     if(b%x==0) b/=x,x=1;if(b%y==0) b/=y,y=1;
    47     if(c%x==0) c/=x,x=1;if(c%y==0) c/=y,y=1;
    48     a%=mod;b%=mod;c%=mod;
    49     return (a*b%mod)*c%mod;
    50 }
    51 LL solve(LL n){
    52     if(n <= 0) return 0;
    53     int len=0;
    54     memset(bit,0,sizeof(bit));
    55     LL m=n;
    56     while(n > 0)
    57         bit[++len]=n%10, n/=10;
    58     //cout<<"n = "<<m<<" ,len = "<<len<<endl;
    59     return ((sum(m)-DP(len,0,0,0,0).second)%mod+mod)%mod;
    60 }
    61 int main()
    62 {
    63     for(int i=1;i<20;i++)
    64         fac[i]=(fac[i-1]*10)%mod;
    65     memset(cnt,-1,sizeof(cnt));
    66     int cases; cin>>cases;
    67     for(int cas=1;cas<=cases;cas++){
    68         LL l,r;
    69         cin>>l>>r;
    70         //scanf("%lld%lld",&l,&r);
    71         cout<<((solve(r)-solve(l-1))%mod+mod)%mod<<endl;
    72     }
    73     return 0;
    74 }
    View Code

     

    转载于:https://www.cnblogs.com/karlvin/p/3347127.html

    展开全文
  • scanf("%I64d%I64d%d",&N,&M,&K); printf("Case #%d: %I64d\n",cas++,solve(M)-solve(N-1)); } return 0; } CodeForces 55D 题意:求可以被其各个位整除的数的个数。 因为出现的数字顶多就是1~9...

    数位dp核心在于状态描述,因为阶段很简单。

    一般都是求有多少个数,当然也有求平方的变态题。

    因为比这个数小的范围定然是从左至右开始小的,那么什么样的前缀对后面子数有相同的结果?

    HDU 3652

    题意:求能被13整除且含有13这样数的个数。

    赤裸裸的两个条件,加上个pre标明下前缀,其实直接开状态也是一样的。整除这个条件可以用余数来表示。余数转移:(mod*10+i)%13

    /* ***********************************************
    Author        :bingone
    Created Time  :2014-12-26 9:45:24
    File Name     :HDU3652.cpp
    ************************************************ */
    
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <string>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #define inf 0x3f3f3f3f
    #define maxn (10+1000)
    typedef long long ll;
    using namespace std;
    int N,M,T;
    int n;
    int dp[25][10][13][13];//pos mod yes  no noand1 yes   
    int dig[20];
    
    int dfs(int pos,int pre,int fg,int md,int limit){
        if (pos<0) return fg&&(md==0);
        if (!limit&&dp[pos][pre][fg][md]!=-1) return dp[pos][pre][fg][md];
        int res=0;
        int last=limit?dig[pos]:9;
        for (int i=0;i<=last;i++){
            res+=dfs(pos-1,i,fg||(pre==1&&i==3),(md*10+i)%13,limit&&(i==last));
        }
        if (!limit) dp[pos][pre][fg][md]=res;
        return res;
    }
    int solve()
    {
    	int len=0;
    	while(n){
    		dig[len++]=n%10;
    		n/=10;
    	}
    	return dfs(len-1,0,0,0,1);
    }
    int main()
    {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    	memset(dp,-1,sizeof(dp));
        while(~scanf("%d",&n))
    	printf("%d\n",solve());
    		
        return 0;
    }


    HDU 3709

    题意:一个数以某点为“平衡点”,计算结果为0.eg: 4139 则 4*2+1*1==9*1

    前面数字当以某个点为平衡点,前面数值是多少,两个条件就能确定了。

    /* ***********************************************
    Author        :bingone
    Created Time  :2014-12-26 12:16:50
    File Name     :HDU3709.cpp
    ************************************************ */
    
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <string>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #define inf 0x3f3f3f3f
    #define maxn (10+1000)
    typedef long long ll;
    using namespace std;
    ll N,M;
    int T;
    int digt[20];
    ll dp[20][20][2000];
    ll dfs(int pos,int piv,int num,int limit)
    {
    	if(pos<0) return num==0;
    	if(!limit && ~dp[pos][piv][num])
    		return dp[pos][piv][num];
    	int last=limit?digt[pos]:9;
    	ll ret=0;
    	for(int i=0;i<=last;i++){
    		int t;
    		t=num+(pos-piv)*i;
    		if(t<0) continue;
    		ret+=dfs(pos-1,piv,t,limit&&(i==last));
    	}
    	if(!limit) dp[pos][piv][num]=ret;
    	return ret;
    }
    ll solve(ll n)
    {
    	int len=0;
    	while(n){
    		digt[len++]=n%10;
    		n/=10;
    	}digt[len]=0;
    	ll ret=0;
    	for(int i=--len;i>=0;i--)
    		ret+=dfs(len,i,0,1);
    	return ret-len;
    }
    int main()
    {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    	memset(dp,-1,sizeof(dp));
    	scanf("%d",&T);
    	while(T--){
    		scanf("%I64d%I64d",&N,&M);
    		printf("%I64d\n",solve(M)-solve(N-1));
    	}
        return 0;
    }


    HDU 4352

    题意:小于给定数字公共子序列长度为K的数字有多少个。

    起初想法是,前面数字的LIS是多少,结束的数字是哪个,但这样会陷入“后效性”的陷阱。同LIS那样定义为以xx为结尾的LIS为多少。

    使用状态压缩,状态表明为前面数字上升子序列为哪几个,同时内含了长度。这个状压很巧妙,值得学习一下。

    /* ***********************************************
    Author        :bingone
    Created Time  :2014-12-26 15:11:26
    File Name     :HDU4352.cpp
    ************************************************ */
    
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <string>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #define inf 0x3f3f3f3f
    #define maxn (10+1000)
    typedef long long ll;
    using namespace std;
    ll N,M;
    int T,K;
    int digt[20];
    ll dp[20][1<<10][11];
    int getlis(int bit)
    {
    	int ret=0;
    	for(int i=0;i<10;i++)
    		if((1<<i) & bit) ret++;
    	return ret;
    }
    int addlis(int bit,int num)
    {
    	if((1<<num) > bit) return ((1<<num) | bit);
    	if((1<<num) & bit) return  bit;
    	bit|=1<<num;
    	for(int i=num+1;i<10;i++)
    		if((1<<i) & bit) return (bit^(1<<i));
    //	return 0;
    }
    ll dfs(int pos,int s,int limit)
    {
    	if(pos<0) return K==getlis(s);
    	if(!limit && ~dp[pos][s][K])
    		return dp[pos][s][K];
    	int last=limit?digt[pos]:9;
    	ll ret=0;
    	for(int i=0;i<=last;i++){
    		int t=addlis(s,i);
    		if(s==0 && i==0) t=0;
    		ret+=dfs(pos-1,t,limit&&(i==last));
    	}
    	if(!limit) dp[pos][s][K]=ret;
    	return ret;
    }
    ll solve(ll n)
    {
    	int len=0;
    	while(n){
    		digt[len++]=n%10;
    		n/=10;
    	}
    	return dfs(len-1,0,1);
    }
    int main()
    {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    	memset(dp,-1,sizeof(dp));
    	scanf("%d",&T);
    	int cas=1;
    	while(T--){
    		scanf("%I64d%I64d%d",&N,&M,&K);
    		printf("Case #%d: %I64d\n",cas++,solve(M)-solve(N-1));
    	}
        return 0;
    }


    CodeForces 55D

    题意:求可以被其各个位整除的数的个数。

    因为出现的数字顶多就是1~9 其最小公倍数是2520.既然要求可以整除,那么前面数字对2520取余,又有哪些数字 就可以判定唯一。

    /* ***********************************************
    Author        :bingone
    Created Time  :2014-12-26 13:43:35
    File Name     :CodeForces 55D
    ************************************************ */
    
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <string>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #define inf 0x3f3f3f3f
    #define maxn (10+1000)
    using namespace std;
    typedef long long ll;
    int T;
    int digt[20],len;
    ll N,M;
    ll f[20][512][2520];
    int check(int bit,int mod){
        for (int i=2;i<=9;i++){
            if (bit&(1<<(i-2))){
                if (mod%i) return 0;
            }
        }
        return 1;
    }
    
    ll dfs(int pos,int bit,int mod,int limit){
        if (pos<0) return check(bit,mod);
        if (!limit && f[pos][bit][mod]!=-1) return f[pos][bit][mod];
        int last=limit?digt[pos]:9;
        ll ret=0;
        for (int i=0;i<=last;i++){
            int nbit=bit;
            if (i>=2) nbit|=1<<(i-2);
            ret+=dfs(pos-1,nbit,(mod*10+i)%2520,limit&&(i==last));
        }
        if (!limit) f[pos][bit][mod]=ret;
        return ret;
    }
    
    ll solve(ll n)
    {
    	len=0;
    	while(n){
    		digt[len++]=n%10;
    		n/=10;
    	}
    	return dfs(len-1,0,0,1);
    }
    
    int main()
    {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    	memset(f,-1,sizeof(f));
        scanf("%d",&T);
    	while(T--){
    		scanf("%I64d%I64d",&N,&M);
    		printf("%I64d\n",solve(M)-solve(N-1));
    	}
        return 0;
    }



    HDU 3507

    中文题。

    以前都是求有多少个,现在求平方和。

    状态很简单,pos,pre,addmod,mulmod 就是满足题中条件。

    那么平方和如何求?当处理到pos,pre,addmod,mulmod,此时若转移到后面的平方和已知。f=num*ten[pos-1] 

    a1^2+a2^2+a3^2....+an^2那么对于pos位置则是(f+a1)^2+....(f+an)^2

    现在要求的是2*f*(a1+a2+a3...+an) 于是我们发现要求数字和和有多少个数字。三个dfs搞定。

    这个题还有一个坑爹之处,能MOD就MOD吧,因为这个WA了1次。

    /* ***********************************************
    Author        :bingone
    Created Time  :2014-12-27 11:39:51
    File Name     :HDU4507.cpp
    ************************************************ */
    
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <string>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #define inf 0x3f3f3f3f
    #define maxn (10+1000)
    #define MOD 1000000007
    typedef long long ll;
    using namespace std;
    int T;
    ll N,M;
    ll ten[20];
    ll dp1[20][10][7][7];/// tot
    ll dp2[20][10][7][7];/// sum
    ll dp3[20][10][7][7];/// square
    int digt[20];
    ll dfs1(int pos,int pre,int addmod,int mulmod,int limit)
    {
        if(pos<=0) return (addmod!=0) && (mulmod!=0);
        if(!limit && ~dp1[pos][pre][addmod][mulmod])
    	   return dp1[pos][pre][addmod][mulmod];
    	int last=limit?digt[pos]:9;
    	ll ret=0;
    	for(int i=0;i<=last;i++){
    		if(i==7) continue;
    		ret=( ret+dfs1(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last)) )%MOD;
    	}
    	if(!limit) dp1[pos][pre][addmod][mulmod]=ret;
    	return ret;
    }
    ll dfs2(int pos,int pre,int addmod,int mulmod,int limit)
    {
        if(pos<=0)
    		if( (addmod==0) || (mulmod==0)) return -1;
    		else return 0;
        if(!limit && ~dp2[pos][pre][addmod][mulmod])
    	   return dp2[pos][pre][addmod][mulmod];
    	int last=limit?digt[pos]:9;
    	ll ret=0;
    	for(int i=0;i<=last;i++){
    		if(i==7) continue;
    		ll tmp=dfs2(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));
    		if(tmp==-1) continue;
    		ll f1=dfs1(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));///刚开始这里写了dp1[][][][]=.其实不对有limit限制
    		ret=(ret+tmp)%MOD;///而且用dp1[][][][]的时候还是addmod,mulmod没有跟dfs1后面一样,dfs2也是同样道理
    		tmp=(ten[pos-1]*f1)%MOD;
    		tmp=(tmp*i)%MOD;
    		ret=(ret+tmp)%MOD;
    	}
    	if(!limit) dp2[pos][pre][addmod][mulmod]=ret;
    	return ret;
    }
    ll dfs3(int pos,int pre,int addmod,int mulmod,int limit)
    {
    	if(pos<=0)
    		if( (addmod==0) || (mulmod==0)) return -1;
    		else return 0;
    	if(!limit && ~dp3[pos][pre][addmod][mulmod])
    	   return dp3[pos][pre][addmod][mulmod];
    	int last=limit?digt[pos]:9;
    	ll ret=0;
    	for(int i=0;i<=last;i++){
    		if(i==7) continue;
    		ll tmp=dfs3(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));
    		if(tmp==-1) continue;
    		ll f1=dfs1(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));
    		ll f2=dfs2(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));
    		ll mul1=i*i;
    		mul1=(mul1*ten[pos-1])%MOD;
    		mul1=(mul1*ten[pos-1])%MOD;
    		mul1=(mul1*f1)%MOD;
    		ll mul2=2*i;
    		mul2=(mul2*ten[pos-1] )%MOD;
    		mul2=(mul2*f2)%MOD;
    		ret=(ret+tmp)%MOD;
    		ret=(ret+mul1)%MOD;
    		ret=(ret+mul2)%MOD;
    	}
    	if(!limit) dp3[pos][pre][addmod][mulmod]=ret;
    	return ret;
    }
    ll solve(ll n)
    {
    	int len=0;
    	while(n){
    		digt[++len]=n%10;
    		n/=10;
    	}
    	///dfs1(len,0,0,0,1);
    	///dfs2(len,0,0,0,1);
    	ll ret=dfs3(len,0,0,0,1);
    	if(ret==-1) return 0;
    	return ret%MOD;
    }
    int main()
    {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    	ten[0]=1;
    	for(int i=1;i<20;i++)
    		ten[i]=(ten[i-1]*10)%MOD;
    	memset(dp1,-1,sizeof(dp1));
    	memset(dp2,-1,sizeof(dp2));
    	memset(dp3,-1,sizeof(dp3));
    	dp1[0][0][0][0]=9;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%I64d%I64d",&N,&M);
    		solve(M);///
    		printf("%I64d\n",((solve(M)-solve(N-1))%MOD+MOD)%MOD);
    	}
        return 0;
    }


    展开全文
  • hdu4507(数位DP)

    2015-08-21 21:03:00
    d[i][j][k][m]代表长度为i的,对7取余为j的,各个位数相加之和对7取余为k的数的平方和, 但是算平方和需要用到这些数的和,这些数的个数。所以用了一个结构体数组保存每种状态的Count,sum1,.sum2; (ago+k1)^2+...

    题目意思: 给定一个区间,求这段区间中,不含7,对7取余为0,各个位数相加之和对7取余为0的数的平方和。

    设d[i][j][k][m]代表长度为i的,对7取余为j的,各个位数相加之和对7取余为k的数的平方和,

    但是算平方和需要用到这些数的和,这些数的个数。所以用了一个结构体数组保存每种状态的Count,sum1,.sum2;

    (ago+k1)^2+(ago+k2)^2+(ago+k3)^2=3*ago^2+2*ago*(k1+k2+k3)+k2^2+k2^2+k3^2;

    =Count1*ago^2+2*ago*sum1+sum2;

    需要注意取模运算和long long

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #define LL long long
    #define MOD 1000000007
    #define maxn 20
    using namespace std;
    const int N=20;
    LL  md[N];
    LL  digit[maxn];
    LL ans=0;
    struct node
    {
       LL Count=0,sum1=0,sum2=0;
    };
    node dp[maxn][7][7][2];
    int visit[maxn][7][7][2];
    node  dfs(int len,int pre,int before, int state,bool fp) //dfs版本的纯属暴力枚举每一个数字,而递推版本的是考虑了前缀的影响
    {
        if(state)
             {
                 node temp;
                 temp.Count=0;
                 temp.sum1=0;
                 temp.sum2=0;
                 return temp;
             }
        if(len==0 && (pre==0 || before==0))
            {
                 node  temp;
                 temp.Count=0;
                 temp.sum1=0;
                 temp.sum2=0;
                 return temp;
            }
        else if(len==0)
            {
                  node  temp;
                 temp.Count=1;
                 temp.sum1=0;
                 temp.sum2=0;
                 return temp;
            }
        if(!fp && visit[len][pre][before][state]== 1) //
        {
             return dp[len][pre][before][state];
        }
        node  ret ;
        int  fpmax = fp ? digit[len] : 9 ;
        for(int i=0;i<=fpmax;i++) //分别算出以i开头的数的方案数,
        {
            node next=dfs(len-1,(((pre*10+i))%7) ,(before+i)%7,i==7 | state,fp && i == fpmax);
            //temp=temp%MOD;
            //ret+=(temp*temp)%MOD;
            LL  ago   = ( i*md[len-1] )%MOD;
            ret.Count = (ret.Count +  next.Count) %MOD;
            ret.sum1  = (ret.sum1  + ( ago*next.Count ) %MOD + next.sum1) %MOD;
            ret.sum2  = ( ret.sum2 + (next.Count* ( (ago*ago )%MOD ) ) %MOD +(2*ago*next.sum1)%MOD + next.sum2 ) %MOD;
        }
        if(!fp)
        {
            dp[len][pre][before][state]= ret;
            visit[len][pre][before][state]=1;
        }
        return  ret;
    }
    
    LL f(LL n)
    {
        int len=0;
        while(n)
        {
            digit[++len] = n % 10;
            n /= 10;
        }
        LL ans=0;
        ans+=dfs(len,0,0,0,true).sum2;
         return ans;
    }
    void init()
    {
        memset(visit,0,sizeof(visit));
    }
    int main()
    {
       // freopen("test.txt","r",stdin);
        int t;
        scanf("%d",&t);
        md[0]=1;
        for(int i=1;i<=N;i++)
            md[i]=(md[i-1]*10)%MOD;
        while(t--)
        {
            init();
            LL n,m;
            scanf("%I64d%I64d",&n,&m);
             LL ans1=f(m);
             LL ans2=f(n-1);
           printf("%I64d\n", (ans1-ans2 + MOD)%MOD );
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/xianbin7/p/4749032.html

    展开全文
  • HDU4507(数位dp,模板)

    2019-03-15 12:03:23
    解题思路:dp[i][h][s]:i代表第几位数,h代表数字和对7的余数,s代表数字对7的余数。 #include<cstdio> #include<cstring> #define ll long long //#define mod 1000000007LL ...ll d[20],p[20];//...

    解题思路:dp[i][h][s]:i代表第几位数,h代表数字和对7的余数,s代表数字对7的余数。

    #include<cstdio>
    #include<cstring>
    #define ll long long
    //#define mod 1000000007LL
    using namespace std;
    ll mod=1e9 + 7;
    ll d[20],p[20];//这边用int会超 
    struct node
    {
    	ll sqnum,cnt,num;
    	node(){
    		cnt=-1;num=sqnum=0;
    	}
    	node(ll a,ll b,ll c):cnt(a),num(b),sqnum(c){
    	}
    }dp[20][8][8];
    node dfs(int l,int h,int s,bool lim)
    {
    	if(l==0) return (h!=0&&s!=0)? node(1,0,0):node(0,0,0);//注意,求得是和7无关的 
    	if(!lim&&dp[l][h][s].cnt!=-1) return dp[l][h][s];//如果没有限制了并且dp[l][h][s]前面已经得出答案了,就直接返回 
    	int k= lim? d[l]:9;//如果有限制,那就最多到d[l],即后面的枚举要小于l位数 
    	node tp,r=node(0,0,0);
    	for(int i=0;i<=k;i++)
    	{
    		if(i==7) continue;
    		tp=dfs(l-1,(h+i)%7,(s*10+i)%7,lim&&i==d[l]);//只有前面的数都恰好等于给定数的值,那么后面的数才是有限制的 
    		r.cnt+=tp.cnt;//加上后面位中符合条件的数 
    		r.cnt%=mod;
    		r.num+=(tp.num+((p[l]*i)%mod)*tp.cnt%mod)%mod;//反正各种记录 
            r.num%=mod;
            r.sqnum+=(tp.sqnum+((2*p[l]*i)%mod)*tp.num)%mod;
            r.sqnum%=mod;
            r.sqnum+=((tp.cnt*p[l])%mod*p[l]%mod*i*i%mod);
            r.sqnum%=mod;
    	}
    	if(!lim)
    	dp[l][h][s]=r;
    	return r;
    }
     
    ll solve(ll a)
    {
    	int l=0;
    	while(a)
    	{
    		d[++l]=a%10;
    		a/=10;
    	}
    	node tp=dfs(l,0,0,true);
    	return tp.sqnum;
    }
    int main()
    {
    	freopen("t.txt","r",stdin);
    	ll T,a,b;
    	scanf("%d",&T);
    	p[1]=1;
        for(int i=2;i<=20;i++) p[i]=(p[i-1]*10)%mod;
        //printf("%lld\n",mod); 
    	while(T--)
    	{
    		scanf("%lld%lld",&a,&b);
    		ll ans=solve(b)-solve(a-1);
    		printf("%lld\n",(ans%mod+mod)%mod);//可能两个相减为负数,所以要变成正的 
    	}
    	return 0;
    }

     

    展开全文
  • 中文题,题意略,老年人康复练习 数位DP, 和一般的不同,这种数位dp统计数字和或者数字平方和 注意取模!!! 代码: #include using namespace std;...struct D{ ll cnt,sum,sum2;
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4507 题目大意 问区间[a,b]不和7有关数字的平方和。 如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关 1、整数中某一位是7;...node d
  • 链接:HDU - 4507 吉哥系列故事——恨7不成妻 题意: 如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关  1、整数中某一位是7;  2、整数的每一位加起来的和是7的整数倍;  3、这个整数是7的整数倍...
  • 题目链接:[kuangbin带你飞]专题十五 数位DP J - 吉哥系列故事――恨7不成妻题意Time Limit:500MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uDescription 单身! 依然单身! 吉哥依然单身! DS级...
  • Time Limit:500MSMemory Limit:32768KB64bit IO Format:%I64d & %I64u Description  单身! 依然单身! 吉哥依然单身! DS级码农吉哥依然单身! 所以,他生平最恨情人节,不管是214还是77,他都...
  • 转载自shiyicode大佬 感谢!...Time Limit:500MS Memory Limit:32768KB 64bit IO Format:%I64d &amp; %I64u Description  单身!   依然单身!   吉哥依然单身!   DS级码农吉哥依然单身! ...
  • <p><img alt="screen shot 2013-11-24 at 6 23 34 pm" src="https://img-blog.csdnimg.cn/img_convert/357b675fcc68454b476d0f5c084d4507.png" /></p><p>该提问来源于开源项目:groovy/groovy-core</p></div>
  • @基于python实现的基本线性回归(高中数学版) 由于毕设的原因,在这里做一些笔记,主要是记录一下pandas...https://www.kesci.com/home/dataset/59e715b76d213335f38d4507 下载好了以后的数据集就是这样的 我这次...
  • <p><img width="1001" alt="screen shot 2018-09-13 at 1 58 49 pm" src="https://img-blog.csdnimg.cn/img_convert/e51029b35f9715746d4507c571c6d928.png" /></p> <h3>Operating System and Browser <p>MacOS, ...
  • 音乐url的拼接

    2019-04-06 15:17:24
    下载音乐,我们必须知道它的url,开始我的思路是在搜索界面搜索歌曲,然后直接用那个网址来解析数据,然后发现,用python请求那个网址它总是跳转到这个...转载于:https://juejin.im/post/5ca8c165e51d4507f74f85aa...
  • <p>https://gist.github.com/cclements/9d5760c0d4507d4f41301dbf35478b74</p> <h2>OS <p>Arch Linux <h2>Target OS <p>Win 7 <h2>Detailed issue explanation</h2><p>该提问来源于开源项目:byt3bl33d3r/...
  • <p><a href="https://gist.githubusercontent.com/pweisenburger/2d86417b8d4507df6cb2/raw/616683e7208e5df402bed65167201770b035c70e/conky-1.9.0+background-change-fix.patch">conky-1.9.0+background-...
  • <p><img alt="screen shot 2014-06-24 at 4 30 12 pm" src="https://img-blog.csdnimg.cn/img_convert/cef5f3857efe13db53a09d4507a59842.png" /></p> <h3>After (resize) <p><img alt="screen shot 2014-06-24 at 4...
  • <img alt="image" src="https://user-images.githubusercontent.com/9346008/36355035-d4507c66-1517-11e8-9c27-ea92fd8f61c2.png" /> <p>So I would keep <code>wrap</code> function there, and let you deal with...
  • md5() 函数

    千次阅读 2019-05-07 07:07:20
    查看更多 https://www.yuque.com/docs/share/c0fb4cd5-6304-4507-b90c-2a41f95d5690
  • F, [2019-10-02T18:08:22.941673 #12693] FATAL – : [c1c6fd44-1e76-4507-9613-24c9d6d0e551] activerecord (5.0.7.2) lib/active_record/relation/finder_methods.rb:353:in raise_record_not_found_exc eption!...
  • PVST 实验

    2017-11-12 18:24:00
    4507#show spanning-tree VLAN0001 Spanning tree enabled protocol ieee Root ID Priority 24577 Address 001d.4555.a080 This bridge is the root Hello Time 2 sec Max Age 20 sec Forwar...
  • <p><img src="https://dl.dropboxusercontent.com/u/100463011/%D0%A1%D0%BD%D0%B8%D0%BC%D0%BE%D0%BA%20%D1%8D%D0%BA%D1%80%D0%B0%D0%BD%D0%B0%202015-06-12%20%D0%B2%2017.45.40.png" width="500" /></p><p>该提问...
  • Code is here: <a href="https://gist.github.com/Foxprodev/bf9375c299cb426c4507e71d881449fa">https://gist.github.com/Foxprodev/bf9375c299cb426c4507e71d881449fa</a> Each time ORA-24418 appears: - ...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 169
精华内容 67
关键字:

d4507