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.  
  26.   read(n, k); //input begins
  27.   readln;
  28.  
  29.   for i := 1 to n do
  30.   begin
  31.     read(c);
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top