Editorial for Sum


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

type bignum=array[0..500] of longint;
var s,ss:string;
    i,l,j,k:longint;
    n,re,t,u:bignum;

procedure conv(s:string;var n:bignum);
var i:longint;
begin
     n[0]:=length(s);
     for i:=1 to n[0] do n[n[0]-i+1]:=ord(s[i])-48;
end;

procedure mul10(x:longint);
var i:longint;
begin
     for i:=t[0] downto 1 do t[i+x]:=t[i];
     for i:=x downto 1 do t[i]:=0;
     t[0]:=t[0]+x;
end;

procedure add(var a:bignum;b:bignum);
var i,mem,max:longint;
begin
     if b[0]>a[0] then max:=b[0] else max:=a[0];
     mem:=0;
     for i:=1 to max do
     begin
          a[i]:=a[i]+b[i]+mem;
          if a[i]>9 then
          begin
               a[i]:=a[i]-10; mem:=1;
          end
          else mem:=0;
     end;
     if mem>0 then
     begin
          inc(max);
          a[max]:=1;
     end;
     a[0]:=max;
end;

procedure mul(var a:bignum;x:longint);
var i,mem:longint;
begin
     mem:=0;
     for i:=1 to a[0] do
     begin
          a[i]:=a[i]*x+mem;
          mem:=a[i] div 10;
          a[i]:=a[i] mod 10;
     end;
     if mem>0 then
     begin
          inc(a[0]);
          a[a[0]]:=mem;
     end;
end;

begin
     readln(s);
     l:=length(s);
     conv(s,n);
     for i:=l downto 1 do
       for j:=1 to 9 do
       begin
            fillchar(t,sizeof(t),0);
            fillchar(u,sizeof(u),0);
            t[0]:=1; u[0]:=1;
            if i<l then
            begin
                 ss:=copy(s,1,l-i);
                 conv(ss,t);
            end;
            if j<n[i] then
            begin
                 for k:=1 to t[0]+1 do
                     if t[k]=9 then t[k]:=0
                     else
                     begin
                          inc(t[k]); break;
                     end;
                 if k>t[0] then t[0]:=k;
            end;
            if i>1 then mul10(i-1);
            if j=n[i] then
            begin
                 if i>1 then
                 begin
                      ss:=copy(s,l-i+2,i-1);
                      conv(ss,u);
                 end;
                 for k:=1 to u[0]+1 do
                     if u[k]=9 then u[k]:=0
                     else
                     begin
                          inc(u[k]); break;
                     end;
                 if k>u[0] then u[0]:=k;
                 add(t,u);
            end;
            if j>1 then mul(t,j);
            add(re,t);
       end;
     for i:=re[0] downto 1 do write(re[i]);
     writeln;
end.

Code mẫu của RR

import java.io.*;
import java.util.*;
import java.math.*;

public class Main
{
    public static final BigInteger ten = BigInteger.valueOf(10);
    public static BigInteger get(int digit, BigInteger n) {
        if (digit == 0 && n.compareTo(ten) < 0) return BigInteger.ZERO;
        if (n.compareTo(BigInteger.ZERO) <= 0) return BigInteger.ZERO;
        BigInteger res = n.divide(ten);
        if (digit > 0 && n.mod(ten).compareTo(BigInteger.valueOf(digit)) >= 0)
            res = res.add(BigInteger.ONE);
        res = res.add(get(digit, n.divide(ten).subtract(BigInteger.ONE)).multiply(ten));
        String buff = n.divide(ten).toString();
        int cnt = 0;
        for(int i = 0; i < buff.length(); i++)
            if (buff.charAt(i) == '0' + digit) cnt++;
        res = res.add(n.mod(ten).add(BigInteger.ONE).multiply(BigInteger.valueOf(cnt)));
        return res;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger n = new BigInteger(br.readLine());
        BigInteger res = BigInteger.ZERO;
        for(int digit = 0; digit < 10; digit++) {
            BigInteger u = get(digit, n);
//          System.out.println(digit + ": " + u);
            res = res.add(u.multiply(BigInteger.valueOf(digit)));
        }
        System.out.println(res);
    }
}

Code mẫu của hieult

import java.util.*;
import java.math.*;
import java.io.*;

public class Main {
    static int a[] = new int[105];
    static int n;
    static String s;
    static BigInteger B[] = new BigInteger[105];
    static BigInteger f[] = new BigInteger[105];
    static BigInteger g[] = new BigInteger[105];

    public static void init(){
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(s.substring(i, i + 1));
        }
        f[0] = BigInteger.ONE;
        g[0] = BigInteger.ZERO;
        for(int i = 1; i <= n; i++) {
            f[i] = f[i - 1].multiply(BigInteger.valueOf(10));
            g[i] = f[i - 1].multiply(BigInteger.valueOf(i));
        }

        B[n] = BigInteger.ZERO;
        for(int i = n - 1; i >= 0; i--){
            B[i] = B[i + 1].add(f[n - i - 1].multiply(BigInteger.valueOf(a[i])));
        }
    }

    public static BigInteger cal(int id, int num){
        BigInteger res = BigInteger.ZERO;
        if(id == n) return res;
        for(int i = 0; i < a[id]; i++){
            if(i == num) res = res.add(f[n - id - 1]);
            res = res.add(g[n - id - 1]);
        }

        if(a[id] == num){
            res = res.add(B[id + 1].add(BigInteger.ONE));
        }
        return res.add(cal(id + 1, num));
    }

    public static void main(String args[]) throws Exception{
        Scanner sc = new Scanner(System.in);
        s = sc.next();
        n = s.length();
        init();
        BigInteger res = BigInteger.ZERO, ret;
        for(int i = 1; i <= 9; i++){
            ret = cal(0, i);
            res = res.add(ret.multiply(BigInteger.valueOf(i)));
        }
        System.out.println(res);
    }
}

Code mẫu của ll931110

#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();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.