hihoCoder #1033 : 交错和 [ 数位dp ]

传送门

#1033 : 交错和

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个数 x，设它十进制展从高位到低位上的数位依次是 a₀, a₁, ..., a_n - 1，定义交错和函数：

f(x) = a₀ - a₁ + a₂ - ... + ( - 1)^n - 1a_n - 1

_例如：

_{f(3214567) = 3 - 2 + 1 - 4 + 5 - 6 + 7 = 4}

_{给定 l, r, k，求在 [l, r] 区间中，所有 f(x) = k 的 x 的和，即：}

输入

输入数据仅一行包含三个整数，l, r, k(0 ≤ l ≤ r ≤ 10¹⁸, |k| ≤ 100)。

输出

输出一行一个整数表示结果，考虑到答案可能很大，输出结果模 10⁹ + 7。

提示

对于样例，满足条件的数有 110 和 121，所以结果是 231 = 110 + 121。

更多样例：

Input

4344 3214567 3

Output

611668829

Input

404491953 1587197241 1

Output

323937411

Input

60296763086567224 193422344885593844 10

Output

608746132

Input

100 121 -1

Output

120

样例输入

100 121 0

样例输出

题解：

转一发：

http://www.tuicool.com/articles/mqUBFz

中文题=_=题目出处来自hihocoder第一次挑战赛，xiaodao出题。

刚开始做的时候脑洞开大了以为是数论专题，后来才发现是数位dp，几个容易易卡住的点：

1.记忆化搜索写的时候要将相同交错和的个数，相同交错和的数字的和分别进行dp

2.对于一位数字和两位数字的计算方式并不相同，要分数字的位数进行讨论。

3.由于结果可能比较大，每一步都需要使用同余定理，以防运算过程中爆long long的情况。

记忆化搜索的思路，

当前的交错和相同的数字的和=sum（待搜索的状态的数字和+当前搜索的数字的大小*当前搜索到的符合条件的数字个数）。

1033

交错和

G++

4ms

0MB

38秒前

查看

结果:Accepted 提交时间:2015-05-08 16:07:41

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <stack>
  6 #include <cctype>
  7 #include <vector>
  8 #include <cmath>
  9 
 10 #define ll long long
 11 
 12 using namespace std;
 13 
 14 const int M = 28;
 15 const int N = 25;
 16 const ll mod = 1000000007;
 17 
 18 typedef struct
 19 {
 20     ll n;
 21     ll s;
 22 }Node;
 23 
 24 Node dp[N][400];
 25 ll base[N];
 26 ll bit[N];
 27 ll yy;
 28 
 29 void pre()
 30 {
 31     base[1]=1;
 32     int i;
 33     for(i=2;i<=20;i++){
 34         base[i]=(base[i-1]*10)%mod;
 35     }
 36 }
 37 
 38 Node dfs(ll pos,ll target,ll limit)
 39 {
 40     Node t;
 41     t.n=t.s=0;
 42     if(pos==0){
 43         if(target==100){
 44             t.n=1;
 45         }
 46         return t;
 47     }
 48     if((limit==0) && dp[pos][target].n!=-1) return dp[pos][target];
 49     ll head,tail,sgn;
 50     tail=limit ? bit[pos] : 9;
 51     if(pos==yy){
 52         head=1;
 53     }
 54     else{
 55         head=0;
 56     }
 57     sgn=((yy-pos)%2) ? (-1) : (1);
 58     for(ll i=head;i<=tail;i++){
 59         Node nt;
 60         nt=dfs(pos-1,target-i*sgn,(limit==1) && (i==tail));
 61         if(nt.n>0){
 62             t.n+=nt.n;
 63             ll q;
 64             q=(nt.n%mod*base[pos])%mod*i%mod;
 65             t.s=((t.s+nt.s)%mod+q)%mod;
 66         }
 67     }
 68     if(limit==0) dp[pos][target]=t;
 69     return t;
 70 }
 71 
 72 ll solve(ll x,ll sum)
 73 {
 74     ll ans=0;
 75     if(x<=0) return 0;
 76     ll bt=0;
 77     while(x)
 78     {
 79         bt++;
 80         bit[bt]=x%10;
 81         x/=10;
 82     }
 83     for(yy=1;yy<=bt;yy++){
 84         memset(dp,-1,sizeof(dp));
 85         ans=(ans+dfs(yy,sum+100,yy==bt).s)%mod;
 86     }
 87     return ans;
 88 }
 89 
 90 int main()
 91 {
 92     pre();
 93     ll l,r,k;
 94     ll ans;
 95     //freopen("data.in","r",stdin);
 96     //scanf("%d",&T);
 97     //for(int ccnt=1;ccnt<=T;ccnt++){
 98     while(cin>>l>>r>>k){
 99     //while(scanf("%d",&n) != EOF) {
100    //     cin<<l<<r<<k;
101         ans=(solve(r,k)-solve(l-1,k)+mod)%mod;
102         cout<<ans<<endl;
103     }
104     return 0;
105 }