我们发现,数字本身并没有什么特别的含义,含义在于数字与数字之间的联系
换而言之,就是石头门数字与数字之间的距离决定了一切
于是我们处理出每个数下一次出现的位置,并将它当作新的字符串
因为是循环同构,所以要跑一遍最小表示法
最后用哈希判重即可
AC-Code (原谅我用了模\(2^{64}\)的哈希)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
const int maxn = 10000 + 5 , maxk = 100 + 5;
const long long md = 101;
unsigned long long ha[maxn];
int s[maxn][maxk];
int rs[maxk];
int n , k;
map<int , int> app;
void work()
{
memset(ha , 0 , sizeof(ha));
scanf("%d%d" , &n , &k);
for (int i = 0 ; i < n ; i++)
{
for (int j = 0 ; j < k ; j++)
{
scanf("%d" , &s[i][j]);
rs[j] = 0;
}
app.clear();
for (int j = 1 ; j <= k ; j++)
{
if (app[s[i][j - 1]])
rs[app[s[i][j - 1]] - 1] = j;
app[s[i][j - 1]] = j;
}
for (int j = 1 ; j <= k ; j++)
{
if (app[s[i][j - 1]])
rs[app[s[i][j - 1]] - 1] = j;
app[s[i][j - 1]] = j;
}
for (int j = 0 ; j < k ; j++)
rs[j] = ((rs[j] - 1 - j) % k + k) % k;
int mi = 0 , mj = 1 , mk = 0 , mt = 0;
while (mi < k && mj < k && mk < k)
{
mt = rs[(mi + mk) >= k ? mi + mk - k : mi + mk] -
rs[(mj + mk) >= k ? mj + mk - k : mj + mk];
if (!mt)
mk++;
else
{
if (mt > 0) mi = mi + mk + 1;
else mj = mj + mk + 1;
if (mi == mj) mj ++;
mk = 0;
}
}
mk = (mi < mj) ? mi : mj;
for (int p = 0 ; p < k ; p++)
ha[i] = ha[i] * md + rs[( mk + p ) % k] + 1;
}
sort(&ha[0] , &ha[n]);
int ans = unique(&ha[0] , &ha[n]) - &ha[0];
printf("%d\n" , ans);
}
int main()
{
int t;
scanf("%d" , &t);
while (t--)
work();
return 0;
}