Is there any EJOI mirror?
I wrote one my problem in my blog: http://codeforces.com/blog/entry/61556 , this problem is with difficult D2B-D1A. now I will write the problem with difficult D1A(maybe this is with other difficult).
time limit: 2 seconds
memory limit: 256 megabytes
there is given a string s. the substring is named half-palindrome if we can do palindrome with change some places of characters(we can do not change this substring). find the number of substrings of s that are half-palindromes(the substring must not be empty).
the length of string is at most 100 000 and all characters are in lower-case and are one of the first 10 characters in alphabet.
example test case:
how to solve it?
I know this but I can not write that because for me is hard speak English. write in comments solution of this task. I hope you enjoyed with solving this task and this blog was usefull for you :).
ian have secuence A of n numbers . ian wroted on a paper all subsecuences of A that length are k. then he wrote the product of numbers for each subsequence on his albom. then he wrote a sum of numbers from albom on a table. what number is on table? for example if n=3 k=2 and subsequence is (2,4,5) on the paper will be: (2,4) (2,5) (4,5) subsequences, in albom numbers: 8 10 20. on a table 8+10+20=38; if n=3 k=1 and subsequence is (2,4,5) answer is: 2+4+5=11;
in a first line two integer numbers, n and k in a next line is the secuence A. each element is positive integer that is not grater than 1 000 000 000;
1≤n≤100 000; 1≤k≤min(n,20); all numbers of sequance A are positive integers that are not grater than 1 000 000 000;
print the number on table with modulo 10^9+7;
Sample Input 0
2 4 5
Sample Output 0
if n=3 k=2 and subsequence is (2,4,5) on the paper will be: (2,4) (2,5) (4,5) subsequences, in albom numbers: 8 10 20. on a table 8+10+20=38;
Sample Input 1
2 4 5
Sample Output 1
if n=3 k=1 and subsequence is (2,4,5) answer is: 2+4+5=11;