矩陣快速冪

演算法學習 – 快速冪和矩陣快速冪(複雜度Olog(n))C 實現

快速冪 快速冪顧名思義,就是快速算某個數的多少次冪。其時間複雜度為 O(log₂N), 與樸素的O(N)相比效率有了極大的提高。 快速冪實現原理 快速冪的原理比較好懂,就是說假如我們求的是3^11,其實比較通用的辦法就是 for 1:11 a*=3; 時間複雜度為O(n), 那麼我們有沒有更快的辦法 […]

BZOJ 1712 [Usaco2007 China] Summing Sums 加密

Description     那N只可愛的奶牛剛剛學習了有關密碼的許多演算法,終於,她們創造出了屬於奶牛的加密方法.由於她們並不是經驗十足,她們的加密方法非常簡單:第i只奶牛掌握著密碼的第i個數字,起始的時候是Ci(0≤Ci<90000000).加密的時候,第i只奶牛會計算其他所有奶牛的數字 […]

【GDOI2018模擬7.12】B 矩陣乘法 dp

Description 給定一個3*3的網格圖,一開始每個格子上都站著一個機器人。每一步機器人可以走到相鄰格子或留在原地,同一個格子上可以有多個機器人。問走n步後,有多少種走法,滿足每個格子上都有機器人。答案對10^9 7取模。 Input 1 Output 229 這題是個大水但是我由於沉迷第一題 […]