题目链接
坑:
1.ll x,y;
z=x*y;可能会溢出,于是我写成x%mod*y%mod
仍旧错误,要写成x%mod*(y%mod).
2.f(9019)=1.
要注意如果为0,下一位的符号根据0的个数而变化
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<string.h>
#include<string>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define re(i,n) for(int i=0;i<n;i++)
;
/*
Node cnt表示个数,sum表示和
*/
struct Node{
ll cnt, sum;
Node() :cnt(), sum(){}
Node(ll c, ll s) :cnt(c), sum(s){}
}dp[][][][];//(bits,+-,+-can change,sum)
/*
19 最多19位
2 +还是-
2 是否是第一个数字
600 f(n)的结果,因为19位*9=171,输入的k是-100到100,所以范围大概是-300到+300,所以用600
*/
ll ten[];
//ten[i]表示10^i
void init(){
ten[] = ;
; i < ; i++){
ten[i] = * ten[i - ];
}
}
/*d是一个大管家,管理者dp这个数组,如果计算过,那就不再计算了
对参数做一些处理,像适配器一样
n表示[0,10^n-1]范围内,第一个符号为flag,符号是否会改变change,f(n)=k
*/
Node d(int n, int flag, int change, int k){
? : );
;
Node f(ll,int, int, int);
){
dp[n][ff][change][kk] = f(ten[n] - , flag, change, k);
}
return dp[n][ff][change][kk];
}
/*
主要逻辑都在这个函数里面,n表示[0,n]范围内的值
*/
Node f(ll n, int flag, int change, int k){
), );
){
&& flag*k <= n), flag*k);
, );
}
ll mi = , h = ;
)h = tmp % , mi++;
mi--;
ll va = h*ten[mi];//处理清楚最高位
Node t = d(mi, change ? : -flag, change, k); //第一位为0时,有多少种情况
Node ans = t;
; i < h; i++){
t = d(mi, -flag, , k - flag*i);
ans.cnt += t.cnt;
ans.sum = (ans.sum + ten[mi]%mod*i*( t.cnt%mod) + t.sum) % mod;
}
//第一位为h时的情况
)?flag:-flag);
){
ff *= -;
}
t = f(n - va, ff, , k - flag*h);
ans.cnt += t.cnt;
ans.sum = (ans.sum + va%mod*(t.cnt%mod) + t.sum) % mod;
return ans;
}
int main(){
//freopen("in.txt", "r", stdin);
init();
memset(dp, -, sizeof(dp));
ll l, r, k;
cin >> l >> r >> k;
Node m = f(l - , ,, k), n = f( r, ,, k);
ll ans = (n.sum - m.sum) % mod;
)ans += mod;
cout << ans << endl;
;
}
别人的代码还精简,算法更好.
struct node
{
ll cnt,sum; //分别表示该状态的出现的次数，以及数字和
node(ll _cnt,ll _sum):cnt(_cnt),sum(_sum){}
node(){}
}dp[][][]; //dp[i][j][k],表示当前在的i位，第一位有效位为j，交错和为k-100的状态
ll num[];
ll ten[];
ll l,r;
int k;
node dfs(int cur,int first,int sum,bool limit)
{
)
);
].cnt != -) ];
;
node ret(,),tv;
rep(i,up+)
{
int g;
? : cur); }
else g = first;
if(g)
tv = dfs(cur-,g,sum+((g-cur)%==?:-)*i,limit && i == up);
else
tv = dfs(cur-,,,limit && i==up);
ll t = i*ten[cur-]%mod;
ret.cnt = (ret.cnt + tv.cnt) % mod; //次数相加
ret.sum = (ret.sum + tv.sum + t*tv.cnt)%mod; //和相加
}
] = ret;
return ret;
}
ll solve(ll n)
{
) ;
;
while(n){
num[++len] = n % ;
n /= ;
}
,,).sum;
}
void init()
{
memset(dp,-,sizeof(dp));
ten[] = ;
;i<;i++) ten[i] = (ten[i-] * ) % mod;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
init();
while(~scanf("%lld%lld%d",&l,&r,&k))
{
cout<<(solve(r)-solve(l-)+mod)%mod<<'\n';
}
;
}