记录编号	100535	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[SPOJ 1433] 代数和	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2014-05-06 11:03:41	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int SIZEL=20;
ll pow10[SIZEL]={1};
char s[SIZEL]={0};//就是N
int L;
int p[SIZEL]={0};
ll suff_free(int &osg,int n,int pk,int sk){//前面符号是是osg,共n位,前缀是p[0]开始的pk位,后面sk位随意
	//if(n<1||pk<0||sk<0) return 0;
	//一共pow10[sk]个数,拆出来pow10[sk]*n个数码
	ll ans=0;
	if(!(n&1)||((n&1)&&!sk)){//总位数是偶数,前缀的符号总是一样的
		//而若总位数是奇数而且sk=0,那么就单独算了一次
		//若总位数是奇数而且sk>0,则前缀和相互抵消掉
		int sgn=osg;
		for(int i=0;i<pk;i++){
			ans+=sgn*(p[i])*pow10[sk];
			sgn*=-1;
		}
	}
	//if(!sk) return ans;//如果没有自由位就不用进行下面的计算了
	if(sk){//如果没有自由位就不用折腾了
		if(n&1){//总位数是奇数
			//我们可以按照末位数字两两分组:(01),(23),(45),(67),(89),每一组前面所有数位一定相同于是抵消掉,和是1或者-1
			int sgn=osg*((n&1)?1:-1);//这里计算了第一个(即:前缀00000)数末尾0的符号
			sgn*=-1;//每一组的和
			ans+=sgn*pow10[sk]/2;//自由位贡献的和
		}
		else{//总位数是偶数
			//每一位上都有pow10[sk]个数,这些数中0~9的出现概率均等,因此平均数都是4.5,每一位上和的绝对值都是pow10[sk]*4.5
			//再来考虑符号,如果有偶数个自由位那么所有位的和两两抵销,否则答案就是pow10[sk]*4.5*(最后一位的符号)
			if(sk&1) ans+=pow10[sk]*4.5*osg*((n&1)?1:-1);
		}
	}
	osg*=(sk>0||!(n&1))?1:-1;//改变osg的值
	return ans;
}
ll calc(void){
	ll ans=0;
	int sgn=1;
	//计算:1~999...9,这里9的个数是L-1
	for(int i=1;i<=L-1;i++){
		//计算有i位的,从100...0到999...9
		for(int k=1;k<=9;k++){
			p[0]=k;
			ans+=suff_free(sgn,i,1,i-1);
		}
	}
	for(int i=1;i<=L;i++){//固定第1~i位
		for(int j=0;j<s[i-1]-'0';j++){//固定第i位为j
			if(i==1&&j==0) continue;
			p[i-1]=j;
			ans+=suff_free(sgn,L,i,L-i);
		}
		p[i-1]=s[i-1]-'0';
	}
	ans+=suff_free(sgn,L,L,0);//N本身
	return ans;
}
int main(){
	freopen("kpsum.in","r",stdin);
	freopen("kpsum.out","w",stdout);
	for(int i=1;i<=18;i++) pow10[i]=10*pow10[i-1];
	scanf("%s",s);
	L=strlen(s);
	printf("%lld\n",calc());
	return 0;
}