A:?HDU5170

這題讓比較a^b與c^d的大小。1<=a,b,c,d<=1000.

顯然這題沒法直接做，要利用對數(shù)來求，但是在math庫中有關(guān)的對數(shù)函數(shù)返回的都是浮點數(shù)，所以這又要涉及到eps問題。

其它就沒有什么需要注意的了，我用的是log()函數(shù)，當(dāng)然還可以用log10().....,原理不變。

#include <iostream> #include <algorithm> #include <math.h> #include <map> #include <queue> #include <stack> #define inf 0x3f3f3f3f #include <stdio.h> #include <string.h> typedef long long ll; #define mod 10000007 #define eps 1e-9 using namespace std; int a,b,c,d; int main() {while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){if(b*log(a)-d*log(c)>eps)printf(">\n");else if(fabs(b*log(a)-d*log(c))<=eps)printf("=\n");else printf("<\n");}return 0; }

?B: HDU5171

題目：按照規(guī)則擴(kuò)展一個集合k次，然后求其總和。

【分析】

擴(kuò)展規(guī)則很簡單，就是一個斐波那契數(shù)列，但是如果按照模擬的方法手動推算，復(fù)雜度對于本題的數(shù)據(jù)范圍來說是不太合適的。（1≤k≤1000000000） 可以利用矩陣快速冪來迅速完成。（矩陣快速冪可以完成任何遞推公式） [0, 1, 0]? [f[n-1],f[n],s[n-1]]*[1, 1, 1] = [f[n],f[n+1],s[n]] [0, 0, 1] 我第一次寫完代碼后驗證結(jié)果是對的，但提交一直WA，之后發(fā)現(xiàn)在計算矩陣A的k+1次冪時，發(fā)現(xiàn)中間爆數(shù)據(jù)了，果斷把int a[3][3]改成了 __int64 a[3][3],果斷A了。 #include <iostream> #include <algorithm> #include <stdio.h> #include <string.h> typedef __int64 ll; #define mod 10000007 using namespace std; struct ma {ll a[3][3]; }res,init; int n,se[100010]; ll sum,k; ma mult(ma x,ma y) {ma temp;for(int i=0;i<3;i++){for(int j=0;j<3;j++){temp.a[i][j]=0;for(int z=0;z<3;z++)temp.a[i][j]=(temp.a[i][j]+x.a[i][z]*y.a[z][j])%mod;}}return temp; } ma Pow(ma x,ll ke) {ma temp;for(int i=0;i<3;i++){for(int j=0;j<3;j++){temp.a[i][j]=(i==j);}}while(ke){if(ke&1) temp=mult(x,temp);ke>>=1;x=mult(x,x);}return temp; } int main() {while(scanf("%d%I64d",&n,&k)!=EOF){sum=0;init.a[0][0]=0,init.a[0][1]=1,init.a[0][2]=0;init.a[1][0]=1,init.a[1][1]=1,init.a[1][2]=1;init.a[2][0]=0,init.a[2][1]=0,init.a[2][2]=1;for(int i=0;i<n;i++){scanf("%d",&se[i]);}sort(se,se+n);for(int i=0;i<n-2;i++){sum=(sum+se[i])%mod;}k+=1;res=Pow(init,k);sum=(sum+(se[n-2]*res.a[0][2])%mod+(se[n-1]*res.a[1][2])%mod+(se[n-2]*res.a[2][2])%mod)%mod;printf("%I64d\n",sum);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhangmingcheng/p/4310933.html

總結(jié)

以上是生活随笔為你收集整理的BC#29A:GTY's math problem（math) B：GTY's birthday gift(矩阵快速幂)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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