Problem

1 /11


Number of subsequences

Theory Click to read/hide

Question 27. Development of a program for processing numerical sequences

To solve this issue, you need to write a program to process a file that contains a sequence of numbers. The A file contains the number of numbers that can be brute-forced. To solve the В file, the enumeration algorithm is no longer suitable, because it will work for a long time and it will be practically impossible to get an answer in a time acceptable for the exam. Therefore, our goal is to learn how to write efficient algorithms for solving such problems.

To successfully complete this task, you must:
  • Know the basics of combinatorics;
  • Know the basics of number theory;
  • Know dynamic programming.
 
Sequence and its subsequences

All numbers from the file form one sequence. A subsequence is obtained from the current sequence by removing any number of elements.

A continuous subsequence is obtained from a sequence by removing any number of elements either from the beginning of the sequence or from the end. 

The number of contiguous subsequences that start with the first element is equal to the number of elements in the whole sequence.
Reading the next number of the sequence, we get a new subsequence. The sum of the elements of the new subsequence is calculated by adding the value of the new element to the sum of the elements of the previous subsequence. The number of elements of the new subsequence will be one more than the number of elements of the previous subsequence.

For example, if s is the sum of the elements of the previous subsequence, and x is the next number in the sequence, then the sum of the elements of the new subsequence is calculated as follows s = s + x.

Problem

Given a sequence of N natural numbers. All its continuous subsequences starting from the first element of the sequence are considered. Find the number of subsequences whose sum is a multiple of K.

Input
The first line contains two numbers: the number of numbers in the sequence N (1 <= N <= 108) and the number K ( 1 <= K <= 100). Next comes N lines, one natural number per line. Each number does not exceed 10000.

Imprint
Display the answer to the problem
 
 
Examples
# Input Output
1 5 3
33
41
19
22
40		 2

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!