SPSUM - Sum
Tác giả: ll931110
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
struct big
{
int d[252];
};
big add(big A,big B)
{
big C;
memset(C.d,0,sizeof(C.d));
for (int i = 0; i < 250; i++)
{
C.d[i] += A.d[i] + B.d[i];
if (C.d[i] > 9)
{
C.d[i + 1]++; C.d[i] -= 10;
}
}
return C;
};
big mul(big A,int x)
{
big C;
memset(C.d,0,sizeof(C.d));
for (int i = 0; i < 250; i++) C.d[i] = A.d[i] * x;
for (int i = 0; i < 250; i++)
{
C.d[i + 1] += C.d[i] / 10; C.d[i] %= 10;
}
return C;
}
big assign(int x)
{
big A;
memset(A.d,0,sizeof(A.d));
A.d[0] = x;
for (int i = 0; i < 12; i++)
{
A.d[i + 1] = A.d[i] / 10; A.d[i] %= 10;
}
return A;
}
string s;
int n;
big d10[255],f10[255];
big ret;
void solve()
{
memset(ret.d,0,sizeof(ret.d));
for (int dig = 1; dig < 10; dig++)
{
big tmp;
memset(tmp.d,0,sizeof(tmp.d));
for (int i = n - 1; i > 0; i--)
{
big r = mul(f10[i],s[i]);
tmp = add(tmp,r); //1st part: lower
if (s[i] > dig) tmp = add(tmp,d10[i]);
else if (s[i] == dig)
{
big D;
memset(D.d,0,sizeof(D.d));
for (int j = 0; j < i; j++) D.d[j] = s[j];
D.d[0]++;
tmp = add(tmp,D);
}
}
if (s[0] >= dig) tmp.d[0]++;
tmp = mul(tmp,dig);
ret = add(ret,tmp);
}
int pos = 249;
while (!ret.d[pos]) pos--;
for (int i = pos; i >= 0; i--) printf("%d", ret.d[i]);
printf("\n");
}
int main()
{
// freopen("sum.inp","r",stdin);
// freopen("sum.out","w",stdout);
cin >> s;
reverse(s.begin(),s.end());
n = s.size();
for (int i = 0; i <= n; i++) s[i] -= '0';
d10[0] = assign(1);
for (int i = 1; i <= n; i++) d10[i] = mul(d10[i - 1],10);
for (int i = 1; i <= n; i++) f10[i] = mul(d10[i - 1],i);
solve();
}