f980 - Ｗｉtｈoｕt Ｍｅ
題目描述
題目要求計算 n 個相異數字進行 Bogo Sort 一次就成功的機率的倒數，並將結果模 P 輸出。Bogo Sort 一次成功的機率為 1/n!，因此題目實際上要求計算 n! mod P。
解題思路
題目給定的 n 的位數最多為 10000，P 最大為 10007。直接計算 n! 可能會超出 long long 的範圍。因此，需要使用模運算來避免溢位。程式碼首先讀取 n 和 P。然後，它計算 n 的每一位數字，並將其添加到答案中。如果答案大於或等於 P，則輸出 0。否則，它計算 (n-1)! mod P，並輸出結果。由於 P 是質數，且 P <= 10007，因此 n! mod P 可以通過迭代計算 (1 * 2 * ... * n) mod P 來實現。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string n;
long long p;
while(cin >> n >> p){
long long ans=0;
for(long long i=0;i<n.size();++i){
ans*=10;
ans+=n[i]-'0';
if(ans>=p)break;
}
if(ans>=p){
cout << "0\n";
}
else{
for(long long i=ans-1;i>1;--i){
ans*=i;
ans%=p;
}
cout << ans << "\n";
}
}
}