补题+知识点hash康托展开

补题+知识点hash康托展开

D. Period

题意要求求出在修改所给的位置p上的字符之后，字符串又多少个周期。

首先又判断，整个字符串不能超过两个周期，因为修改之后的字符是原字符串中所没有的，那么对于修改位置p上的字符而言，每个周期所对应的最后一个字符为p前的一个字符，那么就是看前p-1个字符或者后n-p个字符中能相互对应的有几个。

对于样例ccpc而言，由于c是对应的那么ans[1]++，说明进行周期处理后能对应的字符串长度为1的有1个，比如对于字符串abababa来说ans[1]++,ans[3]++。那么当修改的位置为4的时候，周期就能是6和2一共两个。现在就是如何求前缀和后缀相等的长度的数量，kmp

kmp的next数组表示的含义就是当第i为不匹配的时候前面的最长相等的 前缀和后缀的长度，

即对abababa来说

i01234567abababanext-10010303

那么对于这个串而言，我们需要统计当next[n]不匹配的时候前面相等的长度是多少，然后继续此过程即可。

之后，对整个ans数组作前缀和，ans[x]即表示前后缀相等的长度小于等于x的个数为多少。

然后对于每次询问，处理出其表示的最多的相等的长度，即min（p-1,n-p）;(防止中间出现交叉）

c++里next为保留关键字，不能使用。

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=1e6+5;
int n,nxt[N],ans[N];
string s;
void kmp(){
	int i=0,j=-1;
	nxt[0]=-1;
	while(i>s;
	n=s.size();
	kmp();
	int m;
	cin>>m;
	while(m--){
		int p;
		scanf("%d",&p);
		p=min(p-1,n-p);
		cout<

J. Circular Billiard Table

首先对于题目圆进行分析可得，每两次碰撞之间形成的圆心角的大小即可2*β，那么假设在圆中碰撞了n次那么所形成的圆心角的和就是2*n*β，要保证能够除去，则2*n*β就必须为360的整数倍

即,k为整数，且要求出满足最小的k的n，那么，首先__gcd(a,180*b)可以得到化简之后的分母最小，那么n==180*b/gcd可得到的就是n的最小值，又因为在进入的时候就等效于碰撞了一次，那么输出n-1即可。

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=2e6+5;
const int mod=1e9+7;
int in[N];
void solve(){
	ll a,b;
	scanf("%lld%lld",&a,&b);
	ll n=180*b/__gcd(180*b,a);
	cout<>t;
	while(t--){
		solve();
	}
}

知识点：

hash：

康托展开：实现的是全排列和自然数之间的一一对应的关系，即双射。

其中，an表示的是在该位置后有几个数比其要小的数的个数。

例如：  5 2 4 1 3                 那么进行康托展开后可得

x=4*4！+1*3！+2*2！+0*1！+0*0！=106，那么106就表示该序列在全排列中的序号，

当然，全排列的序号从0开始，即该序列是全排列的第107个序列、

这样可log级别下得到该排列的顺序，

并且由于在dfs或bfs进行的过程中，我们需要保存状态，那么当状态数难以直接进行处理的时候，我们可以采用这种方法来进行该状态与自然数的双射关系，例如一个3*3的1-9的数字矩阵，如果我们用直接拼接来保存状态，那么我们需要1亿的空间进行保存，而其不同的状态只有9！种，无疑是浪费了空间。

康托逆展开

例如上述的5 2 4 1 3 得到的106，那么我们如何从106得知该序列为5 2 4 1 3 呢

从上式进行反推，104/4! = 4 ……10    除以4!得到商为4余数为10，商即是an，那么表示后面有4个比其小的，其值即为5，

10/3！=1…… 4  表示后方有1个比其小的，那么它就是2

4/2！=2…… 0   表示后方有2个比其小的，那么它就是4

0/1！=0…… 0 表示后面有0个比它小的，那么它就是1

0/0！=0…… 0表示后面有0个比它小的，那么它就是3

得到序列5 2 4 1 3建立起了双射关系。

在逆展开的时候可以先将数加入vector中，然后对于得到的商k，就直接取vector[k]，然后删掉vector中的此元素即可。