# E. Split [문제 링크](https://codeforces.com/contest/2148/problem/E) ## Problem Statement Farmer John has an array $a$ containing $n$ positive integers and an integer $k$. Let $a[l,r]$ be a subarray* of $a$. He performs the following procedure to independently determine if subarray $a[l,r]$ is awesome: - Initially, FJ has $k$ empty [multisets](https://en.wikipedia.org/wiki/Multiset), numbered from $1$ to $k$. - Then, for each element $a_i$ ($1 \le i \le n$) in $a$: - If $l \le i \le r$ (that is, $a_i$ is in the subarray $a[l,r]$), he places $a_i$ in multiset $1$, - Otherwise, he places $a_i$ into any multiset he wants **(which may be multiset $1$)**. - Subarray $a[l,r]$ is awesome if there is some way for him to place elements such that, for every value $v$, all multisets contain the same number of elements with value $v$. In other words, he wants to make all multisets contain the exact same elements (ignoring ordering). Output the number of awesome subarrays. ## Input The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. The first line of each test case contains two integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$). The following line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each testcase, output one integer on a new line: the number of awesome subarrays. ## Footnotes For array $a$ of size $n$ and integers $1 \le l \le r \le n$, the subarray $a[l,r]$ denotes the array consisting of the elements $a_l,\ldots,a_r$, in order. ## 풀이 l r 모두 첫 위치에서 시작해 투 포인터로 모든 개수를 세주었다. 똑같이 나누어줄 수 없는 경우 (0이 나오는 경우)는 각 숫자의 등장 횟수가 k의 배수가 아닌 경우 뿐이다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX = 200'001; int n, k; int a[MAX], cnt[MAX], cur[MAX]; bool chk() { for(int i=1;i<=n;i++) { if(cnt[i]%k) return false; } return true; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { cin >> n >> k; memset(cnt, 0, sizeof cnt); for(int i=1;i<=n;i++) { cin >> a[i]; cnt[a[i]]++; } if(!chk()) { cout << "0\n"; } else { memset(cur, 0, sizeof cur); cur[a[1]]++; ll total=0; int l=0, r=1; while(l<n) { l++; while(r<n && (cur[a[r+1]]+1)*k<=cnt[a[r+1]]) cur[a[++r]]++; cur[a[l]]--; total += r-l+1; } cout << total << '\n'; } } } ```