Related studies:
Here
Problem description:
The laboratory of Microbiology department has been attacked by several robbers recently. They robbed and stole many valuable samples of viruses, bacteria, microorganisms. While being in hurry, they broke a tube. The tube contained sample of one of the most dangerous germs called Dangerm. The tube contained exactly one sample of each of the three species (namely Clu, Tron, Flynn) of Dangerm. During the research and test on the day before robbery, our students managed to discover that everyday each Clu turns into 12 Dangerms (3 Clus, 4 Trons and 5 Flynns), each Tron turns into 21 Dangerms (6 Clus, 7 Trons and 8 Flynns) and each Flynn turns into 30 Dangerms (9 Clus, 10 Trons and 11 Flynns). As Dangerm is very dangerous, scientists have set out a meeting and are planning to invent something called Dangkill to destroy all the Dangerms. They are expecting that the invention of Dangkill will take n days and for every thousand Dangerms, one Dangkill is needed. So to know how many Dangkills need to be prepared, scientists need to know how many Dangerms there will be on the nth day. Can you help them?
Input:
Input starts with an integer T (T ≤ 1000) denoting the number of test cases. Each case contains a single integer n (1 ≤ n ≤ 1 000 000 000).
Output:
For each case, print the number of Dangerms that will exist on the nth day modulo 1 000 000 009.
Solution:
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 |
#include <iostream> using namespace std; long long int a[1002][4]; long long int MOD=1000000009; long long int mat[3][3]={{3,6,9},{4,7,10},{5,8,11}}; long long int res[3][3]; long long int result[3]; void multiply(long long int m[3][3],long long int n[3][3]) { long long int mul[3][3]; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { mul[i][j]=0; for(int k=0;k<3;k++) mul[i][j]= (mul[i][j]+(m[i][k]*n[k][j])%MOD)%MOD; } } for(int i=0;i<3;i++) for(int j=0;j<3;j++) res[i][j]=mul[i][j]; } int power(long long int a) { if(a==1) return 1; power(a/2); multiply(res,res); if(a%2) { multiply(mat,res); } return 0; } int main() { long long int sum,n,num; cin>>n; while(n--) { cin>>num; if(num==1) { cout<<3<<endl; continue; } sum=0; //for(int i=0;i<3;i++) //for(int j=0;j<3;j++) res[0][0]=3; res[0][1]=6; res[0][2]=9; res[1][0]=4; res[1][1]=7; res[1][2]=10; res[2][0]=5; res[2][1]=8; res[2][2]=11; power(num-1); cout<<(res[0][0]+res[0][1]+res[0][2]+ res[1][0]+res[1][1]+res[1][2]+ res[2][0]+res[2][1]+res[2][2])%MOD<<endl; } return 0; } /* 4 1 2 3 1000 out: 3 63 1377 358121526 */ |