题目地址：HDU 5187 分凸型与凹型讨论，对于每一种来说，分别有C(n-1,0)+C(n-1,1)+…+C(n-1,n-1)=2^(n-1)种情况，然后合起来共2^n种情况，，有两种重复的，所以共2^n-2中情况。于是快速幂，但是由于mod为LL 型，在快速幂过程中会爆LL。所以在快速幂的乘法时，用快速乘法，原理跟快速幂一模一样。 代码如下：
;#define LL __int64#define pi acos(-1.0)LL mod;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=1100000;LL Mult(LL n, LL k){LL ans=0;while(k>0){if(k&1) ans=(ans+n)%mod;k>>=1;n=(n+n)%mod;}return ans;}LL qsm(LL n, LL k){LL ans=1;while(k>0){if(k&1) ans=Mult(ans,n)%mod;k>>=1;n=Mult(n,n)%mod;}return ans;}int main(){LL n, ans;while(scanf(“%I64d%I64d”,&n,&mod)!=EOF){if(n==1){printf(“%I64d\n”,1%mod);continue ;}ans=qsm(2,n);printf(“%I64d\n”,(ans+mod-2)%mod);}return 0;}
在你生活出现失意和疲惫时能给你一点儿力量和希冀,只愿你幸福快乐。
