• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# 521C

a guest Mar 3rd, 2015 251 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. const
2.  inf = 1000000007;
3.
4. var
5.   ans, sum, pr, suf, cnk1, cnk2, sfs, sf, z, z1: int64;
6.   a, fa: array[-100..100000] of int64;
7.   c: char;
8.   i, n, j, k: longint;
9.
10.
11. function f(i : int64): int64;// count i! here
12. var z : int64;
13. begin
14.   if fa[i]> 0 then f := fa[i] else
15.   begin
16.     if i <= 0 then z := 1
17.     else z := (int64(1)*f(i-1)*i)mod inf;
18.     fa[i] := z;
19.     f := z;
20.   end;
21. end;
22.
23.
24. begin
25.
28.
29.   for i := 1 to n do
30.   begin
32.     val( c, a[i]);
33.     sum := sum + a[i];
34.   end;
35.   if k = 0 then
36.   begin
37.     for i := 1 to n do
38.       ans := (ans * 10 + a[i]) mod inf;
39.     writeln(ans);
40.     halt;
41.   end; // ends.
42.
43.
44.   sum := sum - a[1] - a[n];//in sum i sum all the numbers  of length(j) within range[2,..,n-1]
45.
46.   sfs := sum; pr := a[1]; suf := a[n]; j := 1; z := 1;//sfs is a sum of a[j+1]+...+a[n-1]
47.
48.   cnk1 := (f(n - j - 2) div f(k-2) div f(n - j - k))mod inf;// how many times we meet the numbers in a[2,..,n-1]
49.   cnk2 := (f(n - j - 1) div f(k-1) div f(n - j - k))mod inf;// how many times we meet the numbers on the borders of array
50.   ans := (ans + sum * cnk1 + (pr+suf) * cnk2)mod inf;// here will be the answer
51.
52.
53.   while j < n - k do
54.   begin
55.     inc( j );
56.     sfs := sfs - a[j];// update
57.     if (k = 0) then cnk1 := 0 else
58.
59.     cnk1 := (f(n - j - 2) div f(k-2) div f(n - j - k))mod inf;//update
60.     cnk2 := (f(n - j - 1) div f(k-1) div f(n - j - k))mod inf;//update
61.
62.
63.     sf := (sf + z * a[n-j+1]) mod inf;//last number of length (j-1) in [2,..,n-1] range
64.     z  := (z * 10) mod inf;//when we add new digit to suffix, we multiple it by z( add j-1 zero)
65.     suf := (suf + z * a[n-j+1]) mod inf;//here is number on suffix of array
66.     sum := ((sum - sf) * 10 + sfs) mod inf;//updating sum
67.     pr  :=  (pr * 10 + a[j]) mod inf;//updating preffix
68.     ans := (ans + sum * cnk1 + (pr + suf) * cnk2) mod inf;
69.   end;
70.
71.
72.   writeln(ans);
73. end.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?