Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const
- inf = 1000000007;
- var
- ans, sum, pr, suf, cnk1, cnk2, sfs, sf, z, z1: int64;
- a, fa: array[-100..100000] of int64;
- c: char;
- i, n, j, k: longint;
- function f(i : int64): int64;// count i! here
- var z : int64;
- begin
- if fa[i]> 0 then f := fa[i] else
- begin
- if i <= 0 then z := 1
- else z := (int64(1)*f(i-1)*i)mod inf;
- fa[i] := z;
- f := z;
- end;
- end;
- begin
- read(n, k); //input begins
- readln;
- for i := 1 to n do
- begin
- read(c);
- val( c, a[i]);
- sum := sum + a[i];
- end;
- if k = 0 then
- begin
- for i := 1 to n do
- ans := (ans * 10 + a[i]) mod inf;
- writeln(ans);
- halt;
- end; // ends.
- sum := sum - a[1] - a[n];//in sum i sum all the numbers of length(j) within range[2,..,n-1]
- sfs := sum; pr := a[1]; suf := a[n]; j := 1; z := 1;//sfs is a sum of a[j+1]+...+a[n-1]
- 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]
- 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
- ans := (ans + sum * cnk1 + (pr+suf) * cnk2)mod inf;// here will be the answer
- while j < n - k do
- begin
- inc( j );
- sfs := sfs - a[j];// update
- if (k = 0) then cnk1 := 0 else
- cnk1 := (f(n - j - 2) div f(k-2) div f(n - j - k))mod inf;//update
- cnk2 := (f(n - j - 1) div f(k-1) div f(n - j - k))mod inf;//update
- sf := (sf + z * a[n-j+1]) mod inf;//last number of length (j-1) in [2,..,n-1] range
- z := (z * 10) mod inf;//when we add new digit to suffix, we multiple it by z( add j-1 zero)
- suf := (suf + z * a[n-j+1]) mod inf;//here is number on suffix of array
- sum := ((sum - sf) * 10 + sfs) mod inf;//updating sum
- pr := (pr * 10 + a[j]) mod inf;//updating preffix
- ans := (ans + sum * cnk1 + (pr + suf) * cnk2) mod inf;
- end;
- writeln(ans);
- end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement