题目：
给定一个数 x，设它十进制展从高位到低位上的数位依次是 a0,?a1,?...,?an?-?1，定义交错和函数：
f(x)?=?a0?-?a1?+?a2?-?...?+?(?-?1)n?-?1an?-?1
例如：
f(3214567)?=?3?-?2?+?1?-?4?+?5?-?6?+?7?=?4
给定
输入数据仅一行包含三个整数，l,?r,?k(0?≤?l?≤?r?≤?1018,?|k|?≤?100)。
输出一行一个整数表示结果，考虑到答案可能很大，输出结果模 109?+?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
231
解法：数位dp，dp[pos][aim][len%2]，记录的是，长度为len，从pos以下位置，在没有任何约束的情况下，结果为aim的交错和。增加一维[len%2]是因为len的奇偶性会影响pos后每位的正负性。dp中，sum为所有结果为aim的数的交错和，n为所有结果为aim的数的个数。
代码：
/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;
#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=22;
const LL INF=1e9+7;
int bit[Max];
int len;
int p=0;
struct node
{
LL sum;
LL n;
};
node dp[22][400][2];
LL help[22];
node dfs(int pos,int aim,bool limit,bool stt)
{
node re;
re.n=0;
re.sum=0;
if(pos==0)
{
if(aim==100)
re.n=1;
return re;
}
if(!limit&&!stt&&dp[pos][aim][len%2].n!=-1)
{
return dp[pos][aim][len%2];
}
int end=limit?bit[pos]:9;
int st= stt?1:0;
for(int i=st; i<=end; i++)
{
int add=((len-pos)%2==0?-1:+1);
node next=dfs(pos-1,aim+add*i,limit&&i==end,0);
re.sum=(re.sum+next.sum+next.n*help[pos]*i%INF)%INF;
re.n=(re.n+next.n)%INF;
}
if(!limit&&!stt)
return dp[pos][aim][len%2]=re;
return re;
}
LL getans(LL n,int aim)
{
if(n<=0)
return 0;
p=0;
while(n)
{
bit[++p]=n%10;
n/=10;
}
LL ans=0;
for(len=1; len<=p; len++)
{
ans=(ans+dfs(len,aim+100,len==p,1).sum)%INF;
}
return ans;
}
int main()
{
LL l,r;
int aim;
memset(dp,-1,sizeof dp);
help[1]=1;
for(int i=2;i<22;i++)
help[i]=(help[i-1]*10)%INF;
while(cin>>l>>r>>aim)
{
cout<<(getans(r,aim)-getans(l-1,aim)+INF)%INF<<endl;
}
return 0;
}
原文：http://blog.csdn.net/xiefubao/article/details/45920739