你最愿意做的哪件事，才是你的天赋所在

0%

发表于 Valine：

题目意思

就是给一个矩阵的大小，以及一个区间l~R，现在可以给相邻两个方格+1或者一个方格+2，你可以在矩阵上任意放l~r的高度的方块，使得他们的高度相等，求放方块的方案数

思路

因为相邻两块可以放，所以可以推出任意两块我们是可以修改他们的奇偶性的，根据对称性可以很简单的写出来
首先当nm%2==1的时候答案肯定是$(R-L+1)^nm$,因为肯定存在一个行或者列为奇数，另一个为偶数，这样就能任意把两个格子的奇偶性质互换了，所以可以随便填，我都可以根据后期来改变。
当nm%2==0的时候，考虑从nm的方格中取出2,4,6,8,10···，偶数个格子放奇数，另外的放偶数，只有这样是可以的，因为他们都要成双成对才行，于是我们得到一个答案
令a为偶数的个数，b为奇数的个数，然后得到答案

阅读全文 »

发表于 Valine：

后缀数组详解

算法的目的

首先，明确我们算法的目的

输入=一个字符串str

输出=一个关于str的后缀排序后的数组，如下图

20160205125505545.jpg
目的就是求出这个sa数组，使得sa[i]=j为第i小的后缀所在的位置

阅读全文 »

发表于 Valine：

题目链接

gym102055

思路

首先要明白一个模运算的性质
(a ^ b) % p = ((a % p)^b) % p
$令e=2^{30}+3,r=(q-1)(p-1)$,$找到e在模n下的逆元d，de=1(mod n)$,然后因为$c=f^{2^{30}+3}(mod n)$,此处用欧拉降幂就得到$c=f^{d^{-1}}(mod n)$,运用上面第四条性质就可以得到$c^d=f(mod n)$因为此处的e与n不一定互质，所以用扩展欧几里得求逆元，然后快速幂求解即可，然后中间用上快速乘就可以过了

阅读全文 »

发表于 Valine：

题目链接

HDU3065

思路

初始化注意一下，然后套AC自动机班子匹配字符串即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e4+10;
const int LEN = 2e6+10;
int vi[1000];
int viru=1;
struct Aho{
	struct state{
		int next[26];
		int fail,cnt;
	}st[N];
	queue<int>q;
	int size;
	void init(){
		while(!q.empty())q.pop();
		memset(vi,0,sizeof(vi));
		for(int i=0;i<N;i++){
			memset(st[i].next,0,sizeof(st[i].next));
			st[i].fail=st[i].cnt=0;
		}
		size=1;
		viru=1;
	}
	void insert(char *S){
		int n = strlen(S),now=0;
		for(int i=0;i<n;i++){
			int c = S[i]-'A';
			if(!st[now].next[c])st[now].next[c]=size++;
			now=st[now].next[c];
		}
		st[now].cnt=viru++;
	}
	void build(){
		for(int i=0;i<26;i++)
		if(st[0].next[i])q.push(st[0].next[i]);
		while(!q.empty()){
			int u = q.front();q.pop();
			for(int i=0;i<26;i++){
				if(st[u].next[i])
				st[st[u].next[i]].fail=st[st[u].fail].next[i],q.push(st[u].next[i]);
				else 
				st[u].next[i]=st[st[u].fail].next[i];
			}
		}
	}
	void Get(int u){
		while(u){
			vi[st[u].cnt]++;
			u=st[u].fail;
		}
	}
	void match(char *S){
		int n=strlen(S),now=0;
		for(int i=0;i<n;i++){
			int c = S[i]-'A';
			if(!(c<=25&&c>=0)){
				now=0;
				continue;
			}
			if(st[now].next[c]){
				now=st[now].next[c];
			}
			else {
				now=st[st[now].fail].next[c];
			}
			if(st[now].cnt){
				Get(now);
			}
		}
	}
}aho;
char str[1010][60];
char S[LEN];
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
	aho.init();
	for(int i=1;i<=n;i++){
		scanf("%s",str[i]);
		aho.insert(str[i]);
	}
	scanf("%s",S);
	aho.build();
	aho.match(S);
	for(int i=1;i<=n;i++)
	if(vi[i])printf("%s: %d\n",str[i],vi[i]);
    }
}

发表于 更新于 Valine：

巨巨博客连接

Wiki-AC自动机
B站视频详解
不知道B站视频会不会变换地址，搜”UESTCACM 每周算法讲堂 AC自动机”就有了
因为学过形式语言与自动机，把书上的每个店看成一个状态，每个fail指针看成一个转移函数就可以了

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define MAX_N 1000006
#define MAX_Tot 500005
struct Aho{
	struct state{
		int next[26];
		int fail,cnt;
	}st[MAX_Tot];
	int size;
	queue<int>q;
	void init(){
		while(!q.empty())q.pop();
		for(int i=0;i<MAX_Tot;i++){
			memset(st[i].next,0,sizeof(st[i].next));
			st[i].fail=st[i].cnt=0;
		}
		size=1;
	}
	void insert(char *S){
		int n=strlen(S);
		int now=0;
		for(int i=0;i<n;i++){
			int c=S[i]-'a';
			if(!st[now].next[c])st[now].next[c]=size++;
			now=st[now].next[c];
		}
		st[now].cnt++;
	}
	void build(){
		st[0].fail=-1;
		//根节点的fail指针已经找到，进入队伍中 
		q.push(0);
		while(!q.empty()){
			int u=q.front();q.pop();
			//遍历与根节点的边，其实再想能不能优化这里 
			for(int i=0;i<26;i++){
				//如果存在这条边 
				if(st[u].next[i]){
					if(u==0)st[st[u].next[i]].fail=0;//这里就是位于与根节点连接的状态，他们的fail指针都指向0 
					else{
						int v= st[u].fail;//令当前节点遍历的为父亲节点，不停的往上找他的祖先 
						while(v!=-1){
							if(st[v].next[i])//如果存在一条与u-i-对应的v-i-边，则找到了 
							{
								st[st[u].next[i]].fail=st[v].next[i];
								break;//保证找的是最长的，也就是离u最近的节点 
							}
							v=st[v].fail;
						}
						if(v==-1)st[st[u].next[i]].fail=0;//如果最后没找到，那么就直接等于根节点 
					}
					q.push(st[u].next[i]);//统计完fail之后，直接就入队等待遍历 
				}
			}
		}
	}
	int Get(int u){
		int res=0;
		while(u&&st[u].cnt!=-1){
			res=res+st[u].cnt;
			st[u].cnt=-1;
			u=st[u].fail;
		}
		return res;
	}
	int match(char *S){
		int n=strlen(S);
		int res=0,now=0;
		for(int i=0;i<n;i++){
			int c = S[i]-'a';
			if(st[now].next[c]){
				now = st[now].next[c];
			}
			else{
				int p = st[now].fail;
				while(p!=-1&&st[p].next[c]==0){
					p=st[p].fail;
				}
				if(p==-1)now=0;
				else now = st[p].next[c];
			}
			if(st[now].cnt){
				res=res+Get(now);
			}
		}
		return res;
	}
}aho;
char S[MAX_N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		aho.init();
		int m;
		scanf("%d",&m);
		while(m--){
			scanf("%s",S);
			aho.insert(S);
		}
		scanf("%s",S);
		aho.build();
		printf("%d\n",aho.match(S));
	}
}

发表于 更新于 Valine：

题目链接

莫干山网络赛

D - Find Integer

思路

根据费马大定理(虽然没有证明，但是这个数据是肯定成立的)，n>2的时候无无解，然后就找n=2的时候，发现是勾股数。
然后这里提供一种勾股数的求法
1.a=2n+1的奇数且a>1，若$a^2+b^2=c^2 \&\&a<b<c 则b=2nn+2n,c=2nn+2n+1$
2.a=2n的偶数且a>2，若$a^2+b^2=c^2\&\&a<b<c 则b=nn-1,c=nn+1$

阅读全文 »

发表于 Valine：

题目链接

HDU6732

思路

这道题首先要会卢卡斯定理和一定的离散知识，根据卢卡斯定理，组合数$C(n,m) mod p$相当于n,m转换为p进制之后每一位的组合数再相乘起来。
然后不等于0的情况就是n转换为p进制后大于m转换为p进制后每一位上的数字都比m的大。然后HMBB[i][j]矩阵相当于若有上述情况，则存在一条路径从i->j,K次方的话，就是i->j经过k条路的方案数目。相当于对n，m的每一位来说存在这样一个序列$t_0->t_1->\dots->t_k$,并且这个序列是单挑不递减的，这个序列存在的方案数就是这个矩阵的和，这个序列可以用组合数学。相当于p个箱子，k+1个球，箱子可以为空的方案数，然后转换成p个箱子，k+p+1个球，箱子不为空的情况。接下来把球拍成一行，然后想象一下在球与球之间使用隔板，就可以把它分成p个部分，一共为k+p+1个隔板，选p-1个，所以总方案数就是

阅读全文 »

发表于 更新于 Valine：

题目链接

622f

思路

直接求肯定会超时，然后自然数幂和可以表达为k+1项的多项式。

自然数幂和展开多项式

阅读全文 »

发表于 Valine：

A

输出n个数字不含0，且这个数不能整除他所包含的物质，考虑3的性质，输入33334这类的数字即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		if(n==1)printf("-1\n");
		else {
		for(int i=0;i<n-1;i++)printf("3");
		printf("4\n");
		}
	}
}
阅读全文 »

发表于 Valine：

题目链接

点这里

A

就是求gcd(a,m)=gcd(a+x,m)的个数，把区间对称一下之后，就发现求得是phi(b/g);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll p(ll x,int cnt){
	if(cnt<0)return 0;
	if(cnt==0)return 1;
	for(int i=2;i<=cnt;i++){
		x*=x;
	}
	return x;
}
ll getphi(ll x){
	ll ans = x;
	for(int i=2;1ll*i*i<=x;i++){
		if(x%i==0){
			ans-=ans/i;
			while(x%i==0)x/=i;
		}
	}
	if(x!=1)ans-=ans/x;
	return ans;
}
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		ll a,b;
		scanf("%lld %lld",&a,&b);
		ll g = gcd(a,b);
		b/=g;
		printf("%lld\n",getphi(b));
	}
}
阅读全文 »