Codeforces Round #519 by Botan Investments D

D. Mysterious Crime

题解：因为是$n$n个不同的数，所以先预处理出第一行每个数字的下一个数字是什么，然后去剩下的$m-1$m−1行去寻找满足$loc[num[i][j]].nxt = num[i][j+1]$loc[num[i][j]].nxt=num[i][j+1]，然后$cnt++$cnt++，这样最后找到这第一行的$n$n个数字在$m$m行中出现了$m$m次的数，然后考虑连续子串的情况，方案数就为$len * (len + 1)/2$len∗(len+1)/2(比如$1,2,3$1,2,3都出现了$m$m次，可行子序列为$[1],[2],[3],[1,2],[1,3],[2,3]$[1],[2],[3],[1,2],[1,3],[2,3])。统计一下即可。

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 100100;
struct node{
	int nxt, cnt;
}loc[N];
int num[13][N];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
#endif
	int n,m;
	cin>>n>>m;
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			scanf("%d",&num[i][j]);
		}
	}
	for(int i = 1; i < n; ++i) {
		loc[num[1][i]].nxt = num[1][i + 1];
		loc[num[1][i]].cnt = 1;
	}
	for(int i = 2; i <= m; ++i) {
		for(int j = 1; j < n; ++j) {
			if(loc[num[i][j]].nxt == num[i][j + 1]) loc[num[i][j]].cnt++;
		}
	}
	long long sum = 1, ans = 0;
	for(int i = 1; i < n; ++i) {
		if(loc[num[1][i]].cnt == m) sum++;
		else ans += sum * (sum + 1) / 2, sum = 1;
	}
	if(sum > 0) ans += sum * (sum + 1) / 2;
	cout<< ans << endl;
    return 0;
}