不容易系列之(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));}}