16.03.01【数论、矩阵】

  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<=10^9,2<=ai<=10^9

题解:
我们用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写的