您现在的位置是：主页 > news > 昆明网站建设价格/网站做外链平台有哪些
昆明网站建设价格/网站做外链平台有哪些
admin2025/6/29 3:06:10【news】
简介昆明网站建设价格,网站做外链平台有哪些,网红营销策划方案,农村自建房设计图app#1033 : 交错和 时间限制:10000ms单点时限:1000ms内存限制:256MB描述 给定一个数 x，设它十进制展从高位到低位上的数位依次是 a0, a1, ..., an - 1，定义交错和函数： f(x) a0 - a1 a2 - ... ( - 1)n - 1an - 1 例如&…
#1033 : 交错和
-
100 121 0
样例输出 -
231
描述
给定一个数 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 |
麻烦的是交错和函数，而通过转换 f(x) = a0 - a1 + a2 - ... + ( - 1)n - 1an - 1可以变成 f(x) = a0 - （a1 -（ a2 - （... - an - 1 ））），
递归写的时候就方便了 ，还有一点就是begin_flag标记，因为首位不可以为0，当我们假设首位为0时，F（x）需要新的计算结果newnum，所以begin_flag标记记录下来首位为0的时候，并且首位为0的时候不应该存入DP数组中，不能和首位不为0的情况混合
状态转移：
end_flag==0时表示枚举到最高位（和模板上end_flag一样），begin_flag==0表示枚举首位为0的情况
DP 数组表示 长度len，首位为dig，交错和为sum的个数及和
DP1 数组表示 长度len，首位为0， 交错和为sum的个数及和
DP2 数组表示 0~num（x后len长度的数）中交错和为sum的个数及和
if（end_flag==1 && begin_flag==1 ） DP 【len】【dig】【sum】= ∑ DP【len-1】【k=0~9】【k-sum】
if（end_flag==1 && begin_flag==0） DP1【len】【 0 】【sum】= ∑ DP【len-1】【k=1~9】【k-sum】+DP1【len-1】【0】【sum】
if（end_flag==0 && begin_flag==1） DP2【len】【dig】【sum】= ∑ DP【len-1】【k=1~（num【len-1】-1）】【k-sum】+DP2【len-1】【num【len-1】】【k-sum】+DP1【len-1】【0】【sum】
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <queue>
#define mem(p,k) memset(p,k,sizeof(p));
#define rep(a,b,c) for(int a=b;a<c;a++)
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define inf 0x6fffffff
#define ll long long
using namespace std;
const int N=30010;
const int mod=1e9+7;
struct node{ll n,s;
};
int n,m,tol,k;
int num[30];
ll a,b,ten[22];
node dp[20][10][300],q;
node dfs(int len,int dig,int sum,int begin_flag,int end_flag){node p,t;p.n=0;p.s=0;if(sum<-150 || sum>150)return p;if(len == 0){if(dig == sum){p.n=1,p.s=dig;return p;}else return p;}if(begin_flag==1 && end_flag==1 && dp[len][dig][sum+150].n>=0)return dp[len][dig][sum+150];int endnum=end_flag?9:num[len-1];int newsum=dig-sum;for(int i=0;i<=endnum;i++){if(begin_flag){t=dfs(len-1,i,newsum,1,!end_flag && i==endnum ?0:1);}else t=dfs(len-1,i,sum,i!=0,!end_flag && i==endnum ?0:1);p.n+=t.n;p.s=((p.s+t.s)%mod+(t.n*dig%mod*ten[len])%mod)%mod;}if(end_flag && begin_flag) dp[len][dig][sum+150]=p;return p;
}ll solve(ll n){tol=0;while(n){num[tol++]=n%10;n/=10;}return dfs(tol,0,k,0,0).s;
}
int main(){ten[0]=1;for(int i=1;i<21;i++)ten[i]=ten[i-1]*10%mod;q.n=-1,q.s=0;for(int i=0;i<20;i++)for(int j=0;j<10;j++)for(int k=0;k<300;k++)dp[i][j][k]=q;scanf("%lld%lld%d",&a,&b,&k);printf("%lld\n",(solve(b)-solve(a-1)+mod)%mod);return 0;
}
