网站建设风险分析,网站开发需多少钱,网站 wordpress 公众号,百度下载应用题目链接
题意#xff1a; 一个序列a1#xff0c;a2#xff0c;a3…an 选择一个i#xff0c;然后将序列改成ai,ai-1,…a1,an,an-1,…ai1 可以进行无数次这样的操作 问#xff1a;最多有多少不同的序列产生#xff1f;#xff08;答案mod1e97#xff09;
题解#xf…题目链接
题意 一个序列a1a2a3…an 选择一个i然后将序列改成ai,ai-1,…a1,an,an-1,…ai1 可以进行无数次这样的操作 问最多有多少不同的序列产生答案mod1e97
题解
如果我们把这个序列当做一个环我们可以发现无论怎样操作其实都是这个环只是在环的不同位置中断开 总共有2n中可能用hash哈希判断是否一样即可 我们将原序列延长一倍 这样是为了方便后边的操作这样我们就可以从左端1开始向后取n长度的序列然后hash存值如果第一次出现就num 一遍操作过后将整个序列翻转再进行相同的操作
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn1e69;
ull hash1[maxn];
ull base[maxn];
int a[maxn];
mapull,intmp;
int n;
ull get_hash(int l,int r)
{return hash1[r]-hash1[l-1]*base[r-l1];
}
void hashs()
{for(int i1;i2*n;i){hash1[i]hash1[i-1]*131(a[i]-0);}
}
int main()
{base[0]1;for(int i1;i4e59;i){base[i]base[i-1]*131;}while(cinn){mp.clear();for(int i1;in;i){cina[i];a[ni]a[i];}hashs();ull sum0;int num0;for(int i1;in;i){sumget_hash(i,in-1);if(!mp[sum]){num;}mp[sum]1;}reverse(a1,an*21);//翻转序列hashs();for(int i1;in;i){sumget_hash(i,in-1);if(!mp[sum]){num;}mp[sum]1;}printf(%d\n,num); }return 0;
}
