小明系列故事——師兄幫幫忙

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 65535/32768 K (Java/Others)

Problem Description 小明自從告別了ACM/ICPC之后，就開始潛心研究數(shù)學問題了，一則可以為接下來的考研做準備，再者可以借此機會幫助一些同學，尤其是漂亮的師妹。這不，班里唯一的女生又拿一道數(shù)學題來請教小明，小明當然很高興的就接受了。不過等他仔細讀題以后，發(fā)現(xiàn)自己也不會做，這下小明囧了：如果回復說自己不懂，豈不是很沒面子？
　　所以，他現(xiàn)在私下求你幫忙解決這道題目，題目是這樣的：
　　給你n個數(shù)字，分別是a1,a2,a3,a4,a5……an，這些數(shù)字每過一個單位時間就會改變，假設(shè)上一個單位時間的數(shù)字為a1’,a2’,a3’……an’，那么這個單位時間的數(shù)字a[i] = a[i - 1]’ * K(i == 1的時候a[1] = a[n]’ * K)，其中K為給定的系數(shù)。
　　現(xiàn)在的問題就是求第t單位時間的時候這n個數(shù)字變成了什么了？由于數(shù)字可能會很大，所以只要你輸出數(shù)字對10^9 + 7取余以后的結(jié)果。

Input 輸入數(shù)據(jù)第一行是一個正整數(shù)T，表示有T組測試數(shù)據(jù)；
　　每組數(shù)據(jù)有兩行，第一行包含輸入三個整數(shù)n, t, k，其中n代表數(shù)字個數(shù)，t代表第t個單位時間，k代表系數(shù)；第二行輸入n個數(shù)字ai，代表每個數(shù)字開始的時候是多少。

　　[Technical Specification]
　　T <= 100
　　1 <= n <= 10 ^ 4
　　0 <= t <= 10 ^ 9　　其中 t = 0 表示初始狀態(tài)
　　1 <= k <= 10 ^ 9
　　1 <= ai<= 10 ^ 9

Output 對于每組數(shù)據(jù)請輸出第t單位時間后這n個數(shù)字變成了什么，輸出的時候每兩個數(shù)字之間輸出一個空格，行末不要輸出多余的空格，具體見樣例。
Sample Input 2 3 2 5 1 2 3 3 0 5 1 2 3
Sample Output 50 75 25 1 2 3 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;typedef __int64 INT; const INT MOD = 1000000007; INT que[10005];INT qpower(INT k,INT t) {INT temp = 1;INT ret = k;while(t){if(t & 1) temp *= ret;temp %= MOD; t >>= 1;ret *= ret;ret %= MOD;}return temp; }int main() {int T;scanf("%d",&T);INT n,t,k,temp;while(T--){scanf("%I64d%I64d%I64d",&n,&t,&k);for(int i = 0;i < n;++i)scanf("%I64d",&que[i]);temp = qpower(k,t);for(int i = 0;i < n;++i)que[i] = (que[i] * temp) % MOD;int f = 0;for(int i = (n - t % n) % n;f < n;f++){printf(f? " %I64d":"%I64d",que[i]);i = (i + 1) % n;}printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 4506(快速幂+找规律)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。