HDOJ 5178 zhx竞赛的题目解析是怎样的？

本文共计400个文字，预计阅读时间需要2分钟。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5187

如果n为1的答案方案是1%P，否则答案方案是2^(n-2) - 2。通过递归思考和排除递增和递减两种顺序，想要达到这个状态，只有中间的数是最大的或最小的。

题目链接：acm.hdu.edu.cn/showproblem.php?pid=5187

如果n为1的话答案是1%p，否则答案是2^n-2-2、

仔细思考，除去递增和递减两种顺序外，要想达到这个状态只能是中间的数是最大的或者最小的。当确定了中心，我们再想，如果确立了两边的个数，和两边分别有哪些数，就能确立唯一的一种排法，所以这种就是C(1,n-1)+C(2,n-1)+C(3,n-1)+……C(n-2,n-1) = 2^(n-1)-2，中心有两种，所以答案就是2*(2^(n-1)-2)+2 = 2^n+2.

#include <cstdio>
typedef long long LL;
LL mul(LL a, LL b, LL c)
{
LL ans = 0;
while(b)
{
if(b&1) ans = (ans + a)%c;
a = (a+a)%c;
b >>= 1;
}
return ans;
}
LL Power_mod(LL a,LL b,LL c)
{
LL ans = 1;
while(b)
{
if(b&1) ans = mul(ans, a, c);
a = mul(a, a, c);
b >>= 1;
}
return ans;
}
int main()
{
LL n,p;
while(scanf("%I64d%I64d", &n, &p) !=EOF)
{
if(n == 1) printf("%I64d\n", 1%p);
else printf("%I64d\n", (Power_mod(2,n,p)+p-2)%p);
}
}