Is there any EJOI mirror?

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 167 |

5 | antontrygubO_o | 166 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 156 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

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

task:

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:

input:

aac

output:

5

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;

Input Format

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;

Constraints

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;

Output Format

print the number on table with modulo 10^9+7;

Sample Input 0

3 2

2 4 5

Sample Output 0

38

Explanation 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

3 1

2 4 5

Sample Output 1

11

Explanation 1

if n=3 k=1 and subsequence is (2,4,5) answer is: 2+4+5=11;

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 23:39:39 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|