本来很水的,答案就是(2^n)-2,但是写坑了QAQ
因为原题要求答案要mod P,一开始我是这么干的:
LL ans=pow_mod(,N,P);
ans=(ans-)%P;
if (N==) ans=%P;
printf("%I64d\n",ans);
结果WA了= =
其实应该这样:
LL ans=pow_mod(,N,P);
ans=(ans+P-)%P;
if (N==) ans=%P;
printf("%I64d\n",ans);
注意ans=(ans+P-2)%P这里
因为ans是快速幂取模之后的值,所以可能这个余数小于2。如果这里直接-2就完蛋了。所以要先加个P
附AC Code
那个奇怪的快速幂模板棒棒哒~中间过程也不会超long long
//B #include <iostream>
#include <cstdio>
using namespace std;
#define LL long long LL func(LL a,LL b,LL c) //a*b%c
{
long long ret = ;
while (b)
{
if (b & )
ret = (ret + a) % c;
a = * a % c;
b >>= ;
}
return ret;
}
LL pow_mod(LL a,LL b,LL MOD)
{
if (a==) return ;
LL t=a%MOD,ans=;
while(b)
{
if (b&)
ans=func(ans,t,MOD);
t=func(t,t,MOD);
b>>=;
}
return ans;
} int main()
{
LL N,P;
while(~scanf("%I64d%I64d",&N,&P))
{
LL ans=pow_mod(,N,P);
ans=(ans+P-)%P;
if (N==) ans=%P;
printf("%I64d\n",ans);
} }