Tokitsukaze has a sequence of length n, denoted by a
.
Tokitsukaze can merge two consecutive elements of a
as many times as she wants. After each operation, a new element that equals to the sum of the two old elements will replace them, and thus the length of a will be reduced by 1
.
Tokitsukaze wants to know the maximum possible number of elements that are multiples of p
she can get after doing some operations (or doing nothing) on the sequence a
.
Input
There are several test cases.
The first line contains an integer T (1≤T≤20), denoting the number of test cases. Then follow all the test cases.
For each test case, the first line contains two integers n and p(1≤n,p≤105), denoting the length of the sequence and the special number, respectively.
The second line contains n integers, where the i-th integer (a_i)(1≤(a_i)≤105) is the i-th element ofa
.
It is guaranteed that the sum of n in all test cases is no larger than (10^6)
.
Output
For each test case, output in one line the maximum possible number of elements that are multiples of p after doing some operations.
Sample Input
2
5 3
2 1 3 2 1
3 1
123 456 789
Sample Output
3
3
啊我好菜我好菜我好菜Q^Q
放一道和这个题很类似的https://codeforces.com/problemset/problem/1333/C
题意就是求最大的不相交的和为p的倍数的连续子段的数目。
注意到这样一个性质：对这个数列求前缀和再取模，如果有两个位置的数相等，说明这段区间的和是p的倍数。因此可以求出当前位置取模过后的前缀和的值，如果这个值在map里出现过，就更新ans++，同时清空map并把当前前缀和的值设置为0（因为当前点到之前的点之间有线段覆盖的话，后面的点和之前的点之间就不能有线段了）再添加map[0]=1（别忘了取模后为0的情况）；没有出现过的话就把当前取模过后的前缀和的值添加到map里。
貌似还有DP做法：
last[i]数组记录最后i出现的位置 dp[i]=max(dp[i-1],dp[last[cur]]+1);
#include <bits/stdc++.h>
using namespace std;
int n, p, ans;
int sum[100005] = {0};
int main()
{
int t;
cin >> t;
while(t--)
{
ans = 0;
map<int, int> mp;
scanf("%d%d", &n, &p);
mp[0] = 1;
for(int i = 1; i <= n; i++)
{
int temp;
scanf("%d", &temp);
sum[i] = (sum[i - 1] + temp) % p;
if(mp.count(sum[i]))
{
ans++;
mp.clear();
sum[i] = 0;
mp[0] = 1;
}
else
{
mp[sum[i]] = 1;
}
}
cout << ans << endl;
}
}