不容易系列之(3)—— LELE的RPG難題

12 Sample Output
36 Authorlcy Source
遞推求解專題練習（For Beginner） 
不考慮首尾顏色情況，此時涂法總數是m*（m-1）^(n-1)  即為全集，設m為顏色種數，n為格數；考慮首尾顏色不同，n格涂法總數f（n），假設首顏色是紅色，那么尾色是粉或綠，如果尾格是紅色，那么n-1格則是粉色或綠色滿足首尾顏色不同，n-1格涂法為f（n-1），全集則是f（n）+f（n-1）則有遞歸式f(n)+f(n-1)=m*（m-1）^(n-1)需要注意的是，n=1時f（1）不是m*（m-1）而是m，不滿足遞歸式，遞歸時應該考慮這里，n=1獨立考慮數據類型應該要大一點，這里我是_int64 涉及乘方防止數據溢出，即爆數據#include<stdio.h>_int64 pow(int a,int b){_int64 p=1;while(b--)p=p*a;return p;}_int64 f(int n){_int64 p;if(n==1)p=0;elsep=3*pow(2,n-1)-f(n-1);return p;}int main(){int n;while(~scanf("%d",&n)){if(n==1)printf("3/n");elseprintf("%I64d/n",f(n));}}