hdu 4507 吉哥系列故事——恨7不成妻 (返回平方和的数位dp)

Posted by 111qqz on Thursday, March 17, 2016

TOC

题目链接 题意:如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关—— 1、整数中某一位是7; 2、整数的每一位加起来的和是7的整数倍; 3、这个整数是7的整数倍;

现在问题来了:吉哥想知道在一定区间内和7无关的数字的平方和。

思路;如果是求count的话毫无难度。。。和之前的题目没什么区别。。不多说了。

但是是求平方数。。。一开始我的做法是在dfs中加一个LL 的参数表示当前的和,然后每次到dfs的出口,之前统计count的时候返回的是1,表示找到了满足条件的一个数,那这回就返回平方和。。但是这样做是错的。。。具体为什么错没有想得很明白。。。大概会少算?

然后参考了如下博客: hdu4507解题报告1 hdu4507解题报告2

适牛的博客之数位dp

正解是,之前的dp只统计了一个cnt,这回要同时统计cnt,sum,sqsum(平方和)..

我们先讨论如何求得满足条件的数的和。

我们设某次进入dfs的数是x,当前长度为pos(长度是越来越短的,因为是从高位到低位,对于没有处理到的低位,是按0算的,比如一个五位数xxxxx,第一次dfs以后也许得到4xxxx,x表示没有填的数的位置,实际上这个数就是40000),当前位置要防止的数字是i,考虑其位置,i对这个数的大小(不是和,就是最后要得到的一个数)的贡献是i*10^(pos-1),设为f. 那么当前的数就是f+x. 我们要求的就是所有f+x的和。现在我们考虑当新添加pos位的数字i对于和的贡献。

当新添加i时,相当与把之前的数整体左移了一位,相当于×10(因为之前[1,x]中的每个满足条件的数都乘了10,所以和也乘了10),然后对于新添加的i,它的贡献是i*cnt[x],含义是对于之前[1,x]所有满足条件的每个数,都进行了pos位置填i的操作,所有对于所有满足条件的和一共添加了cnt[x]个i.

**如果写成用递推的式子就是  **

*sum[10*x+i] = 10 * sum[x] + cnt[x]i;//感谢@clq学长

如果用dfs的话式子就是

sum[new_state] = Σ{ sum[old_state] + (number to add at the postion) * (its base) * count[old_state] }。

接下来我们考虑维护平方和,方法类似。

(f+x)^2=ff+xx+2fx.

ff直接可以算,xx..其实就是上一层dfs得到的(f'+x’)^2嘛…也就是sum2[x] (sum2表示平方和)

2fx也可以算,x就是上一个状态的和。

同样,我们考虑现在已经有了x,处理到pos位置,填到该位置的数字是i的时候对平方和的影响。

xx部分在上一个状态处理过了,即为sum2[x], 2f*x 也可以通过sum[x]得到…

**注意ff,同样,对于之前的[1,x]中每个满足的数,都相当于第pos位添加了i,每个数对平方和的贡献都是ii,所以要*cnt[x]… **

以及要不断取模,为了方便写了两个函数来搞,代码看起来清楚一些。。。

哦,还有一个小坑。。取模相减以后可能为负数。。。。记得加MOD…

** **

/* ***********************************************
Author :111qqz
Created Time :2016年03月16日 星期三 10时44分58秒
File Name :code/hdu/4507.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 fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const LL MOD = 1E9+7;
LL l,r;
int digit[30];
LL power[40];
struct node
{
    LL cnt,sum,sq;
    node(){}
    node (LL _cnt,LL _sum,LL _sq):
    cnt(_cnt),sum(_sum),sq(_sq){};
}dp[25][20][20];                
LL Add(LL a,LL b)
{
    LL res = (a+b) %MOD;
    return res;
}
LL Mul(LL a,LL b)
{
    LL res = ((a%MOD)*(b%MOD))%MOD;
    return res;
}
node dfs (int pos,int mod7,int sum7,bool limit)
{
    if (pos==0)
    {
    if (mod7!=0&&sum7!=0) return node(1,0,0);
    else return node (0,0,0);
    }
    if (!limit&&dp[pos][mod7][sum7].cnt!=-1) return dp[pos][mod7][sum7];

    int mx = limit?digit[pos]:9;
    node res ;
    res.cnt=res.sum=res.sq=0;
    for ( int i = 0 ; i <= mx;  i++)
    {
    if (i==7) continue;
    node tmp = dfs(pos-1,(mod7+i)%7,(sum7*10+i)%7,limit&&i==mx);
    res.cnt = Add(res.cnt,tmp.cnt);
    res.sum = Add(res.sum,Add(tmp.sum,Mul(i,Mul(power[pos],tmp.cnt))));
    res.sq  = Add(res.sq,Add(tmp.sq,Mul(2*tmp.sum,i*power[pos])));
    res.sq  = Add(res.sq,Mul(i*power[pos],Mul(i*power[pos],tmp.cnt)));
    }
    if (!limit) dp[pos][mod7][sum7] = res;
    return res;
}
LL solve ( LL n)
{
    int len = 0 ;
    ms (digit,0);
    while (n)
    {
    digit[++len] = n % 10;
    n/=10;
    }
    return dfs(len,0,0,true).sq;
}

void pre()
{
    power[1] = 1;
    for ( int i = 2 ;i  <= 30 ; i++)
    power[i] = (power[i-1]*10LL)%MOD;
}
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
#endif
    pre();
    int T;
    cin>>T;
    ms(dp,-1);
    while (T--)
    {
    scanf("%lld %lld",&l,&r);
    LL ans = solve (r) - solve (l-1);
    while (ans<0) ans +=MOD;
    //  ans = ans % MOD;
    printf("%lld\n",ans);
    }
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付