16.03.01【数论、矩阵】

OI&ACM, OI训练
  1. 第一题 神经错乱数(game.cpp/c/pas/in/out)
  2. 第二题 异或(xor.cpp/c/pas/in/out)
  3. 第三题 斐波那契数列(fib.cpp/pas/c/in/out)

一套看似都是数学的题。。。
50+50+50

第一题 神经错乱数(game.cpp/c/pas/in/out)

空间512M 时限1s
【题目描述】
有这样一种k×k位的十进制数，我们称它为“神经错乱数”，例如k=3时，100010001是这样的一种数字，因为：
1、首先按照从左往右，从上到下的顺序把数字写成一个正方形，像
123
456
789
所以将100010001写下来的话就会变成
100
010
001
2、对这个正方形进行a次横向的翻转操作，例如对
123
456
789
进行一次横向翻转操作将会变成
321
654
987
3、对这个正方形进行b次纵向的翻转操作，例如对
123
456
789
进行一次纵向翻转操作将会变成
789
456
123
4、对这个正方形进行2×c次向左旋转操作，例如对
123
456
789
进行一次向左旋转操作将会变成
369
258
147
5、对这个正方形进行2×d+1次向右旋转操作，例如对
123
456
789
进行一次向右翻转操作将会变成
741
852
963
6、只要你能选定一组正整数(a, b, c, d)，使得在最后的正方形中每一列的和都相同，那么原数就会被成为神经错乱数。
现在，我们想知道，和R位数相同并且大小不超过R的数当中，有多少个数是神经错乱数。
【输入格式】
输入一个正整数R。
数据保证R的位数不超过16位。
【输出格式】
输出一行，包括一个数字，表示有多少个神经错乱数满足要求。
【样例输入】
3
【样例输出】
4

题目挺长的，但是推一推发现满足要求等价于原正方形的每一行和相同
然后就搜索了，看注释吧
第一次没有考虑全，WA了好多。。。

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
#include<cstdio>
#include<cmath>
using namespace std;
int k,ten=1,a[17],b[5],num[10000],sum[40];
long long ans,y;
void Dfs(int x,int minn,int key)//第x行，从minn开始，这一行的和要为key（x==1时随便）
{
	if(x>k) { ans++;return;	}
	for(int i=minn;i<b[x];i++)//当小于b[x]时，后面值的上限没有限制
	  if(x==1||num[i]==key)
	  {
		y=1;
		for(int j=x;j<k;j++) y*=sum[num[i]];//乘法原理
		ans+=y;
	  }
	if(x==1) Dfs(x+1,0,num[b[x]]);//当等于b[x]时，下一行的值要继续DFS
	else if(num[b[x]]==key) Dfs(x+1,0,key);
}
int main()
{
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {a[++k]=ch-'0';ch=getchar();}
    k=sqrt(k);
    for(int i=1;i<=k*k;i++) b[(i-1)/k+1]=b[(i-1)/k+1]*10+a[i];//原正方形每一行的值
    for(int i=1;i<=k;i++) ten*=10;
    for(int i=0;i<ten;i++) //枚举所有可以取到的值
    {
    	for(int j=i;j;j/=10) num[i]+=j%10;//num[i]表示数字i的各位和
    	sum[num[i]]++;//sum[i]表示和为i的个数
    }
    Dfs(1,k==1?0:ten/10,0);
    printf("%lld\n",ans);
}

第二题 异或(xor.cpp/c/pas/in/out)

空间 512M 时限1s
【题目描述】
初始的时候有n个数，第i个数的大小是2^i-1,我们依次处理每一个数，第i次把第i个数变为编号为i的约数的所有数的异或。比如当n为6的时候：
初始6个数为：
1 2 4 8 16 32
第一次操作1不变所以它们还是：
1 2 4 8 16 32
第二次操作2异或1得到：
1 3 4 8 16 32
第三次操作4异或1得到：
1 3 5 8 16 32
第四次操作8异或3异或1得到：
1 3 5 10 16 32
第五次操作16异或1得到：
1 3 5 10 17 32
第六次操作32异或5异或3异或1得到：
1 3 5 10 17 39
现在我们想知道有多少个正整数b使得可以通过从这最后n个数中取出k个异或起来得到。
【输入格式】
第一行三个正整数n，k，p。
【输出格式】
一个数输出满足条件的b的数量mod p的值。
【样例输入】
3 2 5
【样例输出】
3
【数据范围】
30%的数据n<=1000
50%的数据n<=100000
100%的数据n<=10^9，k<=n，p<=100000

题解：
由于这n个数线性无关，答案就是C(n,k) mod p，由于n，k比较大，p比较小，所以做法具体可以参考魏铭的gift那题。

...这写的都是个毛线呀！算了我们还是去找一下这个题吧。。。
国家队训练2010-2011.pdf第三题
恩大概就是这样（什么鬼，完了？）认真看题解吧。。。
中国剩余定理+费马小定理+（扩展）Lucas定理

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
#include<cstdio>
using namespace std;
int n,m,p,tot;
int power(int a,int b,int P)
{
	int re=1;
	for(;b;b>>=1,a=(long long)a*a%P)
		if(b&1) re=(long long)re*a%P;
	return re;
}
int calc(int n,int p,int pk)
{
	if(!n) return 1;
	int ans=1;
	for(int i=2;i<=pk;i++) if(i%p) ans=(long long)ans*i%pk;
	ans=power(ans,n/pk,pk);
	for(int i=2;i<=n%pk;i++) if(i%p) ans=(long long)ans*i%pk;
	return (long long)ans*calc(n/p,p,pk)%pk;
}
int C(int n,int m,int p,int pi,int pk)
{
	int a=calc(n,pi,pk),b=calc(m,pi,pk),c=calc(n-m,pi,pk),k=0;
	for(int i=n;i;i/=pi) k+=i/pi;
	for(int i=m;i;i/=pi) k-=i/pi;
	for(int i=n-m;i;i/=pi) k-=i/pi;
	return (long long)a*power(b,pk/pi*(pi-1)-1,pk)%pk
	*power(c,pk/pi*(pi-1)-1,pk)%pk*power(pi,k,pk)%pk//求逆元用费马小定理
	*(p/pk)%p*power(p/pk,pk/pi*(pi-1)-1,pk)%p;//中国剩余定理
}
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	for(int i=2,j=p,k;j>1;i++)
	  if(!(j%i))
	  {
	  	for(k=1;!(j%i);j/=i) k*=i;
	  	tot=(tot+C(n,m,p,i,k))%p;
	  }
	printf("%d",tot);
}

第三题 斐波那契数列(fib.cpp/pas/c/in/out)

空间512M 时限2s
【题目描述】
有n个大于1的正整数a1,a2,…,an，我们知道斐波那契数列的递推式是f(i)=f(i-1)+f(i-2)，现在我们修改这个递推式变为f(i)=f(i-1)+f(i-2)+r(i-1)，其中r(x)为a1,a2,…,an中为x的约数的个数。现在要求f(m) mod 19940417的值。注：初值f(1)=1,f(2)=1
【输入格式】
第一行两个数n,m。
接下来一行n个正整数a1,a2,…,an。
【输出格式】
输出一行仅一个数，f(m) mod 19940417的值。
【样例输入】
3 7
2 2 3
【样例输出】
33
【数据范围】
30%的数据n<=1000,m<=1000
另外20%的数据n=0,m<=10^9
100%的数据n<=100000,m<=109，2<=ai<=109

题解：
我们用fib(t)表示斐波那契数列的第t项。首先，我们考虑如果对于斐波那契数列的第i项我们对它加一个1并且继续进行后面的递推的话，那么第j项(j>i)的值就是fib(j)+fib(j-i+1)。所以实际上我们可以对于每个ai分别处理，对于ai，它会给最后的答案贡献fib(m mod ai)+fib(ai+(m mod ai))+…+…这些都可以用矩阵乘法搞定。
看CXC写的吧

数论 矩阵