d541 - “∧”形排列
題目描述
題目要求計算 n 的全排列中“∧”形排列的個數，並輸出結果模 1234567 的值。“∧”形排列的定義是存在一個索引 x，使得排列的前 x 個元素遞增，後面的元素遞減。
解題思路
“∧”形排列的數量等於 2^(n-1)。證明如下：
對於一個 n 的排列，我們可以選擇一個峰值的位置 x (1 <= x <= n)。
如果 x = 1，則排列必須是遞減的，只有一種排列方式。
如果 x = n，則排列必須是遞增的，只有一種排列方式。
如果 1 < x < n，則排列的前 x-1 個元素必須是遞增的，後面的 n-x 個元素必須是遞減的。
對於任意一個 x，我們可以在 n-1 個位置上選擇一個元素作為峰值。
因此，總共有 2^(n-1) 種可能的“∧”形排列。
由於題目要求輸出結果模 1234567 的值，我們需要使用模運算來避免整數溢出。
程式碼中 mod 函數計算 2^(p-1) mod 1234567 的值，使用快速冪算法。
複雜度分析
- 時間複雜度: O(log n) (由於使用了快速冪算法)
- 空間複雜度: O(1)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline void write(long long int x) {
long long int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
inline long long int mod(long long int p){
if(p<=1)return p+1;
bool o=p&1;
p>>=1;
long long int tmp=mod(p);
if(o)
return tmp*tmp*2%1234567;
else
return tmp*tmp%1234567;
}
int main(){
long long int p;
while(scanf("%lld",&p)>0){
if(p>0)
write(mod(p-1));
else
putchar_unlocked('0');
putchar_unlocked('\n');
}
}