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.
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