bzoj 4414 数量积

Posted on | Views:

结论题.

  • 结论:对于类似斐波那契数列的,满足 $a_i=a_{i-1}+a_{i-2}(i\ge 2),a_1=a_2$ 的数列 $a$ ,有以下等式成立:

$$
a_1\cdot a_{n+m+1}=a_n\cdot a_m + a_{n+1} \cdot a_{m+1}
$$

  • 等式右边那坨就是我们要求的数量积.即 $v_i\cdot v_j=C\cdot a_{2i+2j+1}$ .
  • 把可以作为数量积的 $O(n)$ 个数全部求出来即可.

证明过程

$sto\ xmk$ .

  • 考虑矩阵乘法.

  • 比较一下最左端的向量和最右端的运算结果即得结论中的等式.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int P;
inline int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=6e5+10;
int n;
int res[MAXN],tot=0;
int main()
{
	int f1=read();
	P=read(),n=read();
	int a=0,b=f1%P;
	for(int i=2;i<=4*n-1;++i)
	{
		int c=add(a,b);
		if((i&1) && (i>=7))
			res[++tot]=mul(c,f1);
		a=b;
		b=c;
	}
	sort(res+1,res+1+tot);
	tot=unique(res+1,res+1+tot)-res-1;
	cout<<tot%P<<endl;
	return 0;
}