题意：
一个序列a1，a2，a3…an
选择一个i，然后将序列改成ai,ai-1,…a1,an,an-1,…ai+1
可以进行无数次这样的操作
问：最多有多少不同的序列产生？（答案mod1e9+7）
题解：
如果我们把这个序列当做一个环，我们可以发现无论怎样操作其实都是这个环，只是在环的不同位置中断开
总共有2n中可能，用hash哈希判断是否一样即可
我们将原序列延长一倍
这样是为了方便后边的操作，这样我们就可以从左端1开始向后取n长度的序列，然后hash，存值，如果第一次出现就num++，
一遍操作过后，将整个序列翻转，再进行相同的操作
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e6+9;
ull hash1[maxn];
ull base[maxn];
int a[maxn];
map<ull,int>mp;
int n;
ull get_hash(int l,int r)
{
return hash1[r]-hash1[l-1]*base[r-l+1];
}
void hashs()
{
for(int i=1;i<=2*n;i++)
{
hash1[i]=hash1[i-1]*131+(a[i]-'0');
}
}
int main()
{
base[0]=1;
for(int i=1;i<=4e5+9;i++)
{
base[i]=base[i-1]*131;
}
while(cin>>n)
{
mp.clear();
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[n+i]=a[i];
}
hashs();
ull sum=0;
int num=0;
for(int i=1;i<=n;i++)
{
sum=get_hash(i,i+n-1);
if(!mp[sum])
{
num++;
}
mp[sum]=1;
}
reverse(a+1,a+n*2+1);//翻转序列
hashs();
for(int i=1;i<=n;i++)
{
sum=get_hash(i,i+n-1);
if(!mp[sum])
{
num++;
}
mp[sum]=1;
}
printf("%d\n",num);
}
return 0;
}
京公网安备 11010502036488号