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 閱讀(176) |
評論 (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 閱讀(214) |
評論 (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 閱讀(211) |
評論 (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 閱讀(230) |
評論 (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 閱讀(374) |
評論 (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 閱讀(294) |
評論 (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 閱讀(319) |
評論 (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 閱讀(227) |
評論 (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 閱讀(305) |
評論 (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 閱讀(492) |
評論 (0) |
編輯 收藏