題目鏈接

題意：

一個序列a1，a2，a3…an
選擇一個i，然后將序列改成ai,ai-1,…a1,an,an-1,…ai+1
可以進(jìn)行無數(shù)次這樣的操作
問：最多有多少不同的序列產(chǎn)生？（答案mod1e9+7）

題解：

如果我們把這個序列當(dāng)做一個環(huán)，我們可以發(fā)現(xiàn)無論怎樣操作其實都是這個環(huán)，只是在環(huán)的不同位置中斷開
總共有2n中可能，用hash哈希判斷是否一樣即可
我們將原序列延長一倍
這樣是為了方便后邊的操作，這樣我們就可以從左端1開始向后取n長度的序列，然后hash，存值，如果第一次出現(xiàn)就num++，
一遍操作過后，將整個序列翻轉(zhuǎn)，再進(jìn)行相同的操作

代碼：

#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);//翻轉(zhuǎn)序列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; }

總結(jié)

以上是生活随笔為你收集整理的Shift and Reverse的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。