[TIOJ] 1354. 池塘裡的青蛙

題目連結:http://tioj.infor.org/problems/1354

---

因為不確定題目的範圍所以先開個long long壓壓驚(?，這題也是一樣，矩陣乘法快速冪，因為把圖用鄰接矩陣存下來後，其的n次方就是任意點走到任一點走n步的可能方法總數。只是因為也不確定題目給的n是否遞增，所以就把他排個序，然後再做矩陣快速冪，理論上應該會比較快(?，複雜度$O(t log_2 t + log_2 n)$

#include <stdio.h>
#include <algorithm>
typedef long long lld;

inline void gn(lld &_){_=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar();}

using std::sort;
using std::swap;

struct inp{
	lld i, val;
};

inline void matrixTimes(lld [][4],lld [][4],lld [][4]);

bool cmp(inp a,inp b){
	return a.val<b.val;
}

int main(){
	lld n;
	gn(n);
	auto v = new inp[n];
	auto ans = new lld[n];
	for(lld i=0;i<n;i++){
		v[i].i=i;
		gn(v[i].val);
	}
	sort(v,v+n,cmp);
	inp k = v[0];
	auto matrix = new lld[4][4];
	auto ta = new lld[4][4];
	auto tb = new lld[4][4];
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			matrix[i][j]=(i==j);
			ta[i][j]=!(i==j);
		}
	}
	while(k.val){
		if(k.val&1){
			auto oao = new lld [4][4];
			matrixTimes(ta,matrix,oao);
			swap(oao,matrix);
		}
		k.val>>=1;
		matrixTimes(ta,ta,tb);
		swap(tb,ta);
	}
	ans[v[0].i] = matrix[0][0];
	for(int i=1;i<n;i++){
		lld k = v[i].val-v[i-1].val;
		auto a = new lld[4][4];
		auto b = new lld[4][4];
		for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)
				a[i][j]=!(i==j);
		while(k){
			if(k&1){
				auto oao = new lld [4][4];
				matrixTimes(a,matrix,oao);
				swap(oao,matrix);
			}
			k>>=1;
			matrixTimes(a,a,b);
			swap(b,a);
		}
		ans[v[i].i] = matrix[0][0];
	}
	for(lld i=0;i<n;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}

inline void matrixTimes(lld a[][4],lld b[][4],lld c[][4]){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			c[i][j]=0;
			for(int k=0;k<4;k++){
				c[i][j] += a[i][k]*b[k][j];
			}
		}
	}
}

---

或是這題其實有通式($\frac{3 \times(-1)^n+3^n}{4}$)，可以透過把矩陣乘法拆開得到，或是解這個遞迴:$a_0=1,a_1=0, a_n=2 \times a_{n-1} + 3 \times a_{n-2}$

#include <stdio.h>
typedef unsigned long long lld;

inline void gn(lld &_){_=0;char c=getchar_unlocked();while(c<'0'||c>'9')c=getchar_unlocked();while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar_unlocked();}

int main() {
    lld t;
    gn(t);
    while(t--){
      lld k;
      gn(k);
      lld n=k;
      lld ans=1;
      lld a=3;
      while(n){
        if(n&1)
          ans*=a;
        a*=a;
        n>>=1;
      }
      printf("%llu\n",(ans+((k&1)?-3:3))/4);
    }
}