学步园

You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist
and plays the songs in that order until all songs have been played. Then it reshuffles and starts playing the list again.

You have a history of the songs that have been played. However, your record of the history of played songs is not complete, as you started recording songs at a certain point in time and a number of songs might already
have been played. From this history, you want to know at how many different points in the future the next reshuffle might occur.

A potential future reshuffle position is valid if it divides the recorded history into intervals of length s(the number of songs in the playlist) with the first and last interval possibly containing less
than s songs and no interval contains a specific song more than once.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

• One line with two integers s and n (1 ≤ s, n ≤ 100000): the number of different songs in the playlist and the number of songs in the recorded playlist history.
• One line with n space separated integers, x₁, x₂, ..., x_n (1 ≤ x_i ≤ s): the recorded playlist history.

Output

Per testcase:

• One line with the number of future positions the next reshuffle can be at. If the history could not be generated by the above mentioned algorithm, output 0.

4
4 10
3 4 4 1 3 2 1 2 3 4
6 6
6 5 4 3 2 1
3 5
3 3 1 1 1
7 3
5 7 3

1
6
0
7

题意：有一个音乐播放器的播放历史记录，它是从某一刻开始到某一刻结束（也就是说记录前和后可能还有其他歌曲记录)，然后播放的方式是1-n先打乱，播放完在打乱，在播放，现在给你一段历史记录，求第一个歌可能的在打乱时的位置。题意不是很好理解。说白了就是第一个样例中，是3 4 4 1 3 2 1 2 3 4，如果在前面添上1,2那就可以构成3次播放1,2,3,4\4,1,3,2\1,2,3,4这样，然后3是在第三个位置为一种情况。

思路：先预处理，把每个位置后面连续n个数字都不同的话就是true。这步可以o（n）实现，然后开头作为第i个位置的每种情况枚举出来，然后去判断能否后面每个位置都是true即可。

代码：

#include <stdio.h>
#include <string.h>

const int N = 100005;
int t, n, s, seq[N], vis[N];
bool first[N], ok[N];

void init() {
	int i;
	memset(first, false, sizeof(first));
	memset(vis, 0, sizeof(vis));
	for (i = 1; i <= n; i++) {
		if (i > s) {
			first[n + 1 - i] = true;
			continue;
		}
		if (vis[seq[i]]) break;
		vis[seq[i]] = 1;
		first[n + 1 - i] = true;
	}
	int num = 0;
	memset(vis, 0, sizeof(vis));
	memset(ok, true, sizeof(ok));
	int flag = 0;
	for (i = s; i >= s - n + 1 && i >= 1; i--) {
		if (vis[seq[i]]) {
			flag = 1;
			num--;
		}
		else num++;
		vis[seq[i]]++;
		if (flag) ok[i] = false;
	}
	if (s - n + 1 >= 1 && num != n) ok[s - n + 1] = false;
	for (i = s - n; i >= 1; i--) {
		if (vis[seq[i]]) num--;
		else num++;
		vis[seq[i]]++;
		if (vis[seq[i + n]] == 1) num--;
		else if (vis[seq[i + n]] == 2) num++;
		vis[seq[i + n]]--;
		if (num != n) ok[i] = false;
	}
}

bool judge(int start) {
	for (int i = start; i <= s; i += n) {
		if (!ok[i])
			return false;
	}
	return true;
}

int solve() {
	int ans = 0;
	init();
	for (int i = 1; i <= n; i++) {
		if (!first[i]) continue;
		int start = (n - i + 2);
		if (judge(start))
			ans++;
	}
	return ans;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &s);
		for (int i = 1; i <= s; i++)
			scanf("%d", &seq[i]);
		printf("%d\n", solve());
	}
	return 0;
}