"紅色病毒"問題
Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3339????Accepted Submission(s): 1422
Problem Description
醫學界發現的新病毒因其蔓延速度和Internet上傳播的"紅色病毒"不相上下,被稱為"紅色病毒",經研究發現,該病毒及其變種的DNA的一條單鏈中,胞嘧啶,腺嘧啶均是成對出現的。
現在有一長度為N的字符串,滿足一下條件:
(1) 字符串僅由A,B,C,D四個字母組成;
(2) A出現偶數次(也可以不出現);
(3) C出現偶數次(也可以不出現);
計算滿足條件的字符串個數.
當N=2時,所有滿足條件的字符串有如下6個:BB,BD,DB,DD,AA,CC.
由于這個數據肯能非常龐大,你只要給出最后兩位數字即可.
現在有一長度為N的字符串,滿足一下條件:
(1) 字符串僅由A,B,C,D四個字母組成;
(2) A出現偶數次(也可以不出現);
(3) C出現偶數次(也可以不出現);
計算滿足條件的字符串個數.
當N=2時,所有滿足條件的字符串有如下6個:BB,BD,DB,DD,AA,CC.
由于這個數據肯能非常龐大,你只要給出最后兩位數字即可.
?
Input
每組輸入的第一行是一個整數T,表示測試實例的個數,下面是T行數據,每行一個整數N(1<=N<2^64),當T=0時結束.
?
Output
對于每個測試實例,輸出字符串個數的最后兩位,每組輸出后跟一個空行.
?
Sample Input
4
1
4
20
11
3
14
24
6
0
?
Sample Output
Case 1: 2
Case 2: 72
Case 3: 32
Case 4: 0
Case 1: 56
Case 2: 72
Case 3: 56
?
Author
Rabbit
?
Source
RPG專場練習賽
如何找到規律
n=1?? --〉B,D??ans= 2=1*2=2^0*2=2^0(2^0+1)
n=2? -->?? ans=6;?????=2*3=2^1*3=2^1(2^1+1)
n=3? --> ans=20?????? =4*5=2^2*5=2^2(2^2+1)
n=4 ---> ans=72????? = 8*9=2*3*9=2^3(2^3+1)
n=k ---->? ???????????? =2^k-1*(2^k-1+1)
于是題目轉化為快速冪問題.....
代碼:
1 /*@coder 龔細軍*/ 2 /*快速冪算法*/ 3 #include<stdio.h> 4 int main() 5 { 6 int t,cnt,ans,i; 7 _int64 n; 8 while(scanf("%d",&t)!=EOF,t) 9 { 10 for(i=1;i<=t;i++) 11 { 12 cnt=2; 13 ans=1; 14 scanf("%I64d",&n); 15 n--; 16 while(n) 17 { 18 if(n&1) 19 { 20 ans*=cnt; 21 ans%=100; 22 n--; 23 } 24 else 25 { 26 cnt*=cnt; 27 cnt%=100; 28 n>>=1; 29 } 30 } 31 printf("Case %d: %d\n",i,(ans*(ans+1))%100); 32 } 33 putchar(10); 34 } 35 return 0; 36 }
?
）...)
