1
#include<stdio.h>
2#define Max_N 1000000000
3#define M 100000000
4int A[2][2]={1,1,1,0};
5int kb[32];
6int D_to_B(int k)
7{
8 int i=0;
9 while(k>=1){
10 kb[i++]=k%2;
11 k/=2;}
12 return i;
13}
14void Multi(int a[2][2],int b[2][2])
15{
16 int i,j,k;
17 int temp[2][2]={0,0,0,0};
18 for(i=0;i<2;i++)
19 for(j=0;j<2;j++)
20 for(k=0;k<2;k++){
21 temp[i][j]+=int((__int64(a[i][k])*b[k][j])%M);
22 temp[i][j]%=M;}
23 for(i=0;i<2;i++)
24 for(j=0;j<2;j++)
25 a[i][j]=temp[i][j];
26}
27int Matrix_Multi(int a[2][2],int k)//a^k
28{
29 int t,i;
30 int temp[2][2]={1,0,0,1};
31 t=D_to_B(k);
32 for(i=t-1;i>=0;i--){
33 Multi(temp,temp);
34 if(kb[i]==1)Multi(temp,a);}
35 return (M+temp[0][0]-1)%M;
36}
37int main()
38{
39 int N,result;
40 while(scanf("%d",&N)!=EOF){
41 result=Matrix_Multi(A,N+1);
42 printf("%d\n",result);
43 }
44 return 0;
45}
posted @
2008-03-06 22:19 zoyi 阅读(174) |
评论 (1) |
编辑 收藏 1#include<iostream>
2using namespace std;
3#define M 98765431
4#define Max_N 50000
5int N,T,sum=0;
6int cows[Max_N];
7int t[32];
8__int64 a,b;
9int D_to_B(int x)
10{
11 int i=0;
12 while(x>=1){
13 t[i++]=x%2;
14 x/=2;}
15 return i;
16}
17void Multi(__int64 a[2][2],__int64 b[2][2])//矩阵a*b
18{
19 __int64 c[2][2];
20 int i,j,h;
21 memset(c,0,sizeof(c));
22 for(i=0;i<2;i++)
23 for(j=0;j<2;j++)
24 for(h=0;h<2;h++){
25 c[i][j]+=M+a[i][h]*b[h][j];//防止c[i][j]<0的情况
26 c[i][j]%=M;}
27 for(i=0;i<2;i++)
28 for(j=0;j<2;j++)
29 a[i][j]=c[i][j];
30}
31void Multi_k(__int64 a[2][2],int x)//a^x
32{
33 int k,i,j;
34 __int64 temp[2][2]={1,0,0,1};
35 k=D_to_B(x);//把x转为二进制
36 for(i=k-1;i>=0;i--){
37 Multi(temp,temp);
38 if(t[i]==1)Multi(temp,a);
39 }
40 for(i=0;i<2;i++)
41 for(j=0;j<2;j++)
42 a[i][j]=temp[i][j];
43}
44void compute_ab()
45{
46 __int64 A[2][2]={N-1,0,1,-1};
47 if(T==1){a=0;b=1;return;}
48 Multi_k(A,T-2);//求bT-1的一步,A^T-2
49 b=(A[1][0]*(N-1)+A[1][1])%M;//这是bT-1，用来求aT的，aT=(N-1)*bT-1
50 a=((N-1)*b)%M;
51 b=(A[1][0]*(N-1)*(N-1)+A[1][1]*(N-2))%M;//利用bT-1求bT
52}
53void solve()
54{
55 int i;
56 __int64 sum_i,result;
57 for(i=0;i<N;i++){
58 sum_i=(sum+M-cows[i])%M;//sum除了第i头牛
59 result=(b*sum_i+a*cows[i])%M;
60 printf("%I64d\n",result);}
61}
62int main()
63{
64 /*freopen("1.in","r",stdin);
65 freopen("3.ans","w",stdout);*/
66 int i;
67 scanf("%d%d",&N,&T);
68 compute_ab();
69 for(i=0;i<N;i++){
70 scanf("%d",&cows[i]);
71 cows[i]%=M;
72 sum+=cows[i];
73 sum%=M;}
74 solve();
75 return 0;
76}
77
posted @
2008-03-05 17:03 zoyi 阅读(211) |
评论 (0) |
编辑 收藏
1#include<iostream>
2using namespace std;
3#define Max_N 100
4#define Max 60
5typedef struct bigint{
6 int data[Max];
7 int len;
8 friend bigint operator+(bigint,bigint);
9 friend bigint operator*(bigint,bigint);
10 void operator=(const bigint&y){
11 this->len=y.len;
12 for(int i=0;i<y.len;i++)
13 this->data[i]=y.data[i];
14 }
15}BIGINT;
16BIGINT Trees[Max_N+1];
17BIGINT operator+(BIGINT x,BIGINT y)
18{
19 BIGINT r;
20 int rlen=x.len>y.len?x.len:y.len;
21 int tmp,i,jinwei=0;
22 for(i=0;i<rlen;i++){
23 tmp=x.data[i]+y.data[i]+jinwei;
24 r.data[i]=tmp%10;
25 jinwei=tmp/10;}
26 if(jinwei)r.data[rlen++]=jinwei;
27 r.len=rlen;
28 return r;
29}
30void print(BIGINT x)
31{
32 for(int i=x.len-1;i>=0;i--)
33 printf("%d",x.data[i]);
34 printf("\n");
35}
36BIGINT operator*(BIGINT x,BIGINT y)
37{
38 BIGINT r;
39 int i,j;
40 memset(r.data,0,sizeof(r.data));
41 r.len=x.len+y.len;
42 for(i=0;i<x.len;i++)
43 for(j=0;j<y.len;j++)
44 r.data[i+j]+=x.data[i]*y.data[j];
45 for(i=0;i<r.len;i++){
46 r.data[i+1]+=r.data[i]/10;
47 r.data[i]%=10;}
48 while(r.data[i]){
49 r.data[i+1]+=r.data[i];
50 r.data[i]%=10;
51 i++;}
52 while(i>=0&&!r.data[i])i--;
53 r.len=i+1;
54 return r;
55}
56void init()
57{
58 int i,j;
59 memset(Trees,0,sizeof(Trees));
60 Trees[0].data[0]=1;
61 Trees[0].len=1;
62 for(i=1;i<=Max_N;i++)
63 for(j=0;j<i;j++)
64 Trees[i]=Trees[i]+Trees[j]*Trees[i-j-1];
65}
66int main()
67{
68 int n;
69 init();
70 while(scanf("%d",&n)!=EOF)
71 print(Trees[n]);
72 return 0;
73}
posted @
2008-03-02 17:10 zoyi 阅读(208) |
评论 (2) |
编辑 收藏
这道题是问题求解和程序设计的作业题，刚拿到这道题的时候，我完全没与递推的概念，第一反应完全是离散数学里面叫得容斥原理，典型的错排问题，一共有n对新人，有m对是错误的，首先通过c(n,m)选出错误的新人是哪些，然后就是算出这m对新人错误排列的方法。
根据容斥原理的公式推出m对错误的情况有m!-c(m,1)(m-1)!+c(m,2)(m-2)!+.....+(-1)^mc(m,m)0!;
在乘上c(n,m)就好了
化简后得a(n,m)(1-1/1!+1/2!-....+(-1)^m/m!);
算到这里我就犯愁了，这括号了的这些个东西怎么算阿，脑子完全堵住了，缓过神来才发现，要实现它并不困难
程序如下：
1#include<stdio.h>
2__int64 f(int n,int m){
3 __int64 r,tmp1=1;
4 int i;
5 for(i=n;i>n-m;i--)
6 tmp1*=i;
7 r=tmp1;
8 for(i=1;i<=m;i++){
9 tmp1=(-tmp1)/i;
10 r+=tmp1;}
11 return r;
12}
13int main(){
14 int t,m,n;
15 __int64 result;
16 scanf("%d",&t);
17 while((t--)>0){
18 scanf("%d%d",&n,&m);
19 result=f(n,m);
20 printf("%I64d\n",result);
21 }
22 return 0;
23}
posted @
2008-03-02 17:03 zoyi 阅读(227) |
评论 (1) |
编辑 收藏 这道题改了两天，里面用到了整数因子分解，筛选素数，求欧拉函数，
以下是和partychen的聊天记录，既然他把那么难敲得证明都
敲出来了，那我就只接捻好了HOHO~~
主要公式：
sima(N/pi)*pi另外这个公式是可积的陈俊奎 10:13:35
m的约数为x1,x2,x3...xp
陈俊奎 10:13:48
n的约数为y1,y2,y3....yp
陈俊奎 10:14:05
那么有gcd(xi,yi)=1
陈俊奎 10:15:14
那么m*n的任意约数T，有唯一分解T=xi*yj
陈俊奎 10:16:47
T*E(m*n/T)=xi*yi*E(m/xi* n/ yj)=xi*E(m/xi)*yj*E(n / yj)
陈俊奎 10:18:09
f(m*n)=sima(xi*E(m/xi)*yj*E(n / yj))=(sima(xi*E(m/xi))*(sima(yj*E(n/ yj)))=f(m)*f(n)
陈俊奎 10:19:31
f(12)=f(2^2)*f(3)
陈俊奎 10:20:00
f(3)=1*E(3)+3*E(1)=2+3=5
陈俊奎 10:21:14
f(2^2)=1*E(2^2)+2*E(2)+4*E(1)=(2-1)*2^(2-1)+2*(2-1)+4*1
陈俊奎 10:21:25
=2+2+4=8
1#include<iostream>
2using namespace std;
3#define Max_N 50000
4#define Max_P 5200
5#define __int64 _int64
6int Prime[Max_N];//对素数的标记
7int P_div[Max_P];//存储素数约数
8int P_mi[Max_P];//存储素数约数的幂
9void init()//筛选素数
10{
11 _int64 i,j;
12 for(i=2;i<Max_N;i++)
13 if(!Prime[i])
14 for(j=2;j*i<Max_N;j++)Prime[j*i]=1;
15}
16_int64 phi(int p,int e)//欧拉
17{
18 if(e==0||p==1)return 1;
19 if(e==1)return p-1;
20 _int64 i;
21 _int64 result=1;
22 for(i=1;i<e;i++)
23 result*=p;
24 result*=(p-1);
25 return result;
26}
27int get(int i,int e)
28{
29 int j;
30 int r=1;
31 for(j=e;j<P_mi[i];j++)
32 r*=P_div[i];
33 return r;
34}
35int factorization(int n)//整数因子分解
36{
37 int i,j=0;
38 for(i=2;i<Max_N&&n>1;i++)
39 if(!Prime[i]&&n%i==0){
40 P_div[j]=i;
41 while(n%i==0){
42 ++P_mi[j];
43 n/=i;}
44 j++;}
45 if(i>=Max_N||!j){//好重要的疏漏！！！大素数因子没有存入P_div中
46 P_div[j]=n;//吸取教训的地方！！
47 P_mi[j++]=1;}
48 return j;
49}
50int main()
51{
52 //freopen("1.in","r",stdin);
53 //freopen("1.ans","w",stdout);
54 int N;
55 int i,j,t,h,tmp1;
56 _int64 tmp2;
57 _int64 result,p;
58 memset(Prime,0,sizeof(Prime));
59 init();
60 while(scanf("%d",&N)!=EOF){//
61 result=1;
62 memset(P_div,0,sizeof(P_div));
63 memset(P_mi,0,sizeof(P_mi));
64 t=factorization(N);
65 for(i=0;i<t;i++){
66 for(p=0,j=0,h=1;j<=P_mi[i];j++){
67 tmp1=get(i,j);
68 tmp2=phi(P_div[i],j);
69 p+=tmp2*tmp1;}
70 result*=p;}
71 printf("%I64d\n",result);
72 }
73 return 0;
74}
posted @
2008-03-01 20:19 zoyi 阅读(372) |
评论 (0) |
编辑 收藏鸟巢原理
&&fflush害死人的错
1#include<iostream>
2using namespace std;
3#define Max_N 100001
4int c,n,i,j,tem;
5char t;
6int candy[Max_N];
7int sum[Max_N];
8int b[Max_N];
9int main()
10{
11
12 sum[0]=0;
13 while(1){
14 scanf("%d%d",&c,&n);
15 getchar();
16 if(!c&&!n)break;
17 if(!c){printf("no sweets\n");continue;}
18 memset(candy,0,sizeof(candy));
19 memset(b,0,sizeof(b));
20 for(i=1;i<=n;i++){
21 while(t=getchar()){//通过getchar的方法来读数
22 if(t==' '||t=='\n')break;
23 candy[i]=10*candy[i]+t-'0';}
24 if(!(candy[i]%c)){//如果读到的数能被c整除，就已经可以了
25 printf("%d\n",i);
26 break;}
27 sum[i]=(sum[i-1]+candy[i])%c;//如果当前读到的所有数之和也满足情况，这样也行
28 if(!sum[i]){
29 for(j=1;j<=i;j++){
30 printf("%d",j);
31 if(j!=i)putchar(' ');
32 else putchar('\n');
33 }
34 break;}
35 }
36 for(j=i+1;j<=n;j++)scanf("%d",&tem);
37 if(i>n)//处理剩下的一众情况
38 for(i=1;i<=n;i++){
39 if(!b[sum[i]])
40 b[sum[i]]=i;
41 else {
42 for(j=b[sum[i]]+1;j<=i;j++){
43 printf("%d",j);
44 if(j!=i)putchar(' ');
45 else putchar('\n');
46 }
47 break;}}
48
49 }
50 return 0;
51}
posted @
2008-02-27 22:02 zoyi 阅读(293) |
评论 (0) |
编辑 收藏这道题刚开始看懂题时，我是死活不敢动手，就是不相信就是这么做，后来用百度搜了搜这题，在一个博客上看到他对这题的想法，简单的模拟，我这才开始写，值得一提的是，这道题帮助我发现了个我不好的习惯，今天因为这个习惯，使两道题都tl，我总是在没读完数据，输出结果后，就经过一个fflush来刷干净缓冲，但是把结束条件也刷掉了，使程序断不了，导致tl。（这都多些partychen :-)）
1#include<iostream>
2using namespace std;
3#define Max 100
4int main()
5{
6 int n,m,r,c,cont;
7 int i,j,p,q,t;
8 int map[Max][Max];
9 char row[Max];
10 while(scanf("%d%d%d%d",&n,&m,&r,&c)){
11 getchar();
12 memset(map,0,sizeof(map));
13 if(!n&&!m&&!r&&!c)break;
14 cont=0;
15 t=0;
16 for(i=0;i<n;i++){
17 gets(row);
18 for(j=0;j<m;j++){
19 if(map[i][j]!=row[j]-'0')
20 if(i+r<=n&&j+c<=m){
21 for(q=i;q<i+r;q++)
22 for(p=j;p<j+c;p++){
23 map[q][p]+=1;
24 map[q][p]%=2;}
25 cont++;}
26 else {t=1;break;}
27 }
28 if(t==1)break;
29 }
30 if(t==1){
31 while((++i)<n)gets(row);
32 printf("-1\n");}
33 else printf("%d\n",cont);
34 }
35 return 0;
36}
posted @
2008-02-27 21:58 zoyi 阅读(315) |
评论 (0) |
编辑 收藏http://acm.pku.edu.cn/JudgeOnline/problem?id=2356
discuss里说用鸽巢原理，我感觉我写出来的应该是o(n)，可是程序跑了500多
1#include<stdio.h>
2#include<algorithm>
3using namespace std;
4#define Max_N 10000
5struct node{
6 int num;
7 int yu;
8};
9int N;
10int get[Max_N];
11struct node sum[Max_N];
12bool cmp(struct node a,struct node b)
13{
14 if(a.yu<b.yu)return true;
15 else if(a.yu==b.yu)return a.num<b.num;
16 else return false;
17}
18void solve()
19{
20 int i,j;
21 sum[0].yu=get[0]%N;
22 sum[0].num=0;
23 for(i=1;i<N;i++){
24 sum[i].yu=sum[i-1].yu+get[i];
25 sum[i].yu%=N;
26 sum[i].num=i;}//第一个数是get的第一个数，第二个数是前两个数的和取余，一共是N个数，就有N个和
27 //若其中一个和取余是0，显然成立，否则根据鸽巢原理，N个数占N-1个位子，显然会有一样的
28 sort(sum,sum+N,cmp);
29 if(!sum[0].yu){
30 printf("%d\n",sum[0].num+1);
31 for(i=0;i<=sum[0].num;i++)
32 printf("%d\n",get[i]);
33 return;
34 }
35 else {
36 for(i=0;i<N-1;i++)
37 if(sum[i].yu==sum[i+1].yu){
38 printf("%d\n",sum[i+1].num-sum[i].num);
39 for(j=sum[i].num+1;j<=sum[i+1].num;j++)
40 printf("%d\n",get[j]);
41 return;}
42
43 }
44 printf("0\n");
45}
46int main()
47{
48 int i;
49 while(scanf("%d",&N)!=EOF){
50 for(i=0;i<N;i++){
51 scanf("%d",&get[i]);
52 }
53 solve();}
54 return 0;
55}
以下是经过学习别人代码后重写的代码，0ms
1#include<iostream>
2using namespace std;
3#define Max_N 10001
4int main()
5{
6 int N,i,j;
7 int get[Max_N];
8 int sum[Max_N];
9 int b[Max_N];
10 sum[0]=0;
11 memset(b,0,sizeof(b));
12 scanf("%d",&N);
13 for(i=1;i<=N;i++){
14 scanf("%d",&get[i]);
15 if(!(get[i]%N)){
16 printf("1\n%d\n",get[i]);break;}
17 else {
18 sum[i]=(sum[i-1]+get[i])%N;
19 if(!sum[i]){
20 printf("%d\n",i);
21 for(j=1;j<=i;j++)
22 printf("%d\n",get[j]);
23 break;}
24 }
25 }
26 if(i>N){
27 for(i=1;i<=N;i++){
28 if(!b[sum[i]])
29 b[sum[i]]=i;
30 else{
31 printf("%d\n",i-b[sum[i]]);
32 for(j=b[sum[i]]+1;j<=i;j++)
33 printf("%d\n",get[j]);
34 break;}
35 }
36 }
37 return 0;
38}
posted @
2008-02-26 20:39 zoyi 阅读(225) |
评论 (0) |
编辑 收藏这道题是冲着他是数论题去做的，开始对他给的这个式子
seed(x+1) = [ seed(x) + STEP ] % MOD很困惑，然后就开始翻算法导论，刚刚看完解模线性方程，看这个式子和这种方程长得有点相像，就在反复琢磨，钻牛角尖，突然眼睛一亮，想到了，模加法，这就是个以MOD的群，这道题就变成了，初始的A值是什么的情况下，使得子群的模为MOD
是在A和MOD互质的情况下，这道题就迎刃而解了
下面是代码：
1#include<stdio.h>
2int EUCLD(int a,int b)
3{
4 if(!b)return a;
5 else return EUCLD(b,a%b);
6}
7int main()
8{
9 int STEP,MOD,d;
10 while(scanf("%d%d",&STEP,&MOD)!=EOF)
11 {
12 d=EUCLD(STEP,MOD);
13 printf("%10d%10d",STEP,MOD);
14 if(d==1)printf(" Good Choice\n\n");
15 else printf(" Bad Choice\n\n");
16 }
17 return 0;
18}
posted @
2008-02-25 20:30 zoyi 阅读(302) |
评论 (0) |
编辑 收藏 1#include<stdio.h>
2#include<string.h>
3int main()
4{
5 const char Haab_m[19][10]={"pop","no","zip","zotz","tzec","xul","yoxkin","mol","chen","yax",
6 "zac","ceh","mac","kankin","muan","pax","koyab","cumhu","uayet"};
7 const char Tzolkin_d[20][10]={"imix","ik","akbal","kan","chicchan","cimi","manik","lamat","muluk","ok",
8 "chuen","eb","ben","ix","mem","cib","caban","eznab","canac","ahau"};
9 int i,n,Day,Year,total_d;
10 int Y,Di,M,tem_d;
11 char Month[10];
12 scanf("%d",&n);
13 printf("%d\n",n);
14 while((n--)>0){
15 scanf("%d. %s %d",&Day,&Month,&Year);
16 total_d=365*Year;
17 for(i=0;i<19;i++)
18 if(strcmp(Month,Haab_m[i])==0){
19 total_d+=Day+1;
20 break;}
21 else total_d+=20;
22 if(i==19)total_d+=Day+1;
23 tem_d=total_d%260;
24 if(!tem_d){
25 Y=total_d/260-1;
26 M=13;
27 Di=19;}
28 else {
29 Y=total_d/260;
30 M=tem_d%13;
31 Di=(tem_d+19)%20;
32 if(!M)M=13;}
33 printf("%d %s %d\n",M,Tzolkin_d[Di],Y);
34 }
35 return 0;
36}
posted @
2008-02-25 19:33 zoyi 阅读(489) |
评论 (0) |
编辑 收藏