我想用 C 語言撰寫這個公式：
(2<=n<=1e5), (1<=k<=n), (2<=M<=1e9).
我想在不使用特殊結構的情況下做到這一點。不幸的是，在這個公式中有很多情況會有效地使調制變得困難。示例：((n-k)!) mod M can be equal to 0，或者((n-1)(n-2))/4可能不是整數。我將不勝感激任何幫助。
uj5u.com熱心網友回復：
(n?1)!/(n?k)! 可以通過計算乘積 (n?k 1)…(n?1) 來處理。
(n-1)！(n-1)(n-2)/4 可以通過分別處理 n ≤ 2 (0) 和 n ≥ 3 (3…(n-1) (n-1)(n-2)/2) 來處理。
未經測驗的 C ：
#include <cassert>
#include <cstdint>
class Residue {
public:
// Accept int64_t for convenience.
explicit Residue(int64_t rep, int32_t modulus) : modulus_(modulus) {
assert(modulus > 0);
rep_ = rep % modulus;
if (rep_ < 0)
rep_ = modulus;
}
// Return int64_t for convenience.
int64_t rep() const { return rep_; }
int32_t modulus() const { return modulus_; }
private:
int32_t rep_;
int32_t modulus_;
};
Residue operator (Residue a, Residue b) {
assert(a.modulus() == b.modulus());
return Residue(a.rep() b.rep(), a.modulus());
}
Residue operator-(Residue a, Residue b) {
assert(a.modulus() == b.modulus());
return Residue(a.rep() - b.rep(), a.modulus());
}
Residue operator*(Residue a, Residue b) {
assert(a.modulus() == b.modulus());
return Residue(a.rep() * b.rep(), a.modulus());
}
Residue QuotientOfFactorialsMod(int32_t a, int32_t b, int32_t modulus) {
assert(modulus > 0);
assert(b >= 0);
assert(a >= b);
Residue result(1, modulus);
// Don't initialize with b 1 because it could overflow.
for (int32_t i = b; i < a; i ) {
result = result * Residue(i 1, modulus);
}
return result;
}
Residue FactorialMod(int32_t a, int32_t modulus) {
assert(modulus > 0);
assert(a >= 0);
return QuotientOfFactorialsMod(a, 0, modulus);
}
Residue Triangular(int32_t a, int32_t modulus) {
assert(modulus > 0);
return Residue((static_cast<int64_t>(a) 1) * a / 2, modulus);
}
Residue F(int32_t n, int32_t k, int32_t m) {
assert(n >= 2);
assert(n <= 100000);
assert(k >= 1);
assert(k <= n);
assert(m >= 2);
assert(m <= 1000000000);
Residue n_res(n, m);
Residue n_minus_1(n - 1, m);
Residue n_minus_2(n - 2, m);
Residue k_res(k, m);
Residue q = QuotientOfFactorialsMod(n - 1, n - k, m);
return q * (k_res - n_res) * n_minus_1
(FactorialMod(n - 1, m) - q) * k_res * n_minus_1
(n > 2 ? QuotientOfFactorialsMod(n - 1, 2, m) *
(n_res * n_minus_1 Triangular(n - 2, m))
: Residue(1, m));
}
uj5u.com熱心網友回復：
正如其他答案中提到的，除法階乘可以直接評估而無需除法。您還需要 64 位算術來存盤您的子結果。并在每次乘法后使用模數，否則您將需要非常大的數字，這將花費很長時間來計算。
此外，您提到的((n-1)(n-2))/4可能不僅僅是整數如何處理這是有問題的，因為我們對您正在做的事情沒有任何背景。但是，您可以/2在括號之前移動（應用它，(n-1)!因此modpi不要2注意不要將已修改的階乘除以！！！）然后您就沒有余數了，因為(n-1)*(n-2)/4變成了，(n-1)*(n-2)/2并且(n-1)*(n-2)總是奇數（可被 2 整除）。唯一的“問題”是當n=2作為n*(n-1)/2是1，但/2移動前支架將圓下來(n-1)!，所以你應該把它處理由不動的特殊情況/2括號之前（不包括在下面的代碼）。
我是這樣看的：
typedef unsigned __int64 u64;
u64 modpi(u64 x0,u64 x1,u64 p) // ( x0*(x0 1)*(x0 2)*...*x1 ) mod p
{
u64 x,y;
if (x0>x1){ x=x0; x0=x1; x1=x; }
for (y=1,x=x0;x<=x1;x ){ y*=x; y%=p; }
return y;
}
void main()
{
u64 n=100,k=20,m=123456789,a,b,b2,c,y;
a =modpi(n-k 1,n-1,m); // (n-1)!/(n-k)!
b =modpi(1,n-1,m); // (n-1)! mod m
b2=modpi(3,n-1,m); // (n-1)!/2 mod m
c =((n*(n-1)))%m; // 2*( n*(n-1)/2 (n-1)*(n-2)/4 ) mod m
c =(((n-1)*(n-2))/2)%m;
y =(((a*(k-n))%m)*(n-1))%m; // ((n-1)!/(n-k)!)*(k-1)*(n-1) mod m
y =b; // (n-1)! mod m
y-=(((a*k)%m)*(n-1))%m; // ((n-1)!/(n-k)!)*k*(n-1) mod m
y =(b2*c)%m; // (n-1)!*( n*(n-1)/2 (n-1)*(n-2)/4 ) mod m
// here y should hold your answer
}
但是要小心，舊的編譯器不完全支持 64 位整數，可能會產生錯誤的結果，甚至無法編譯。在這種情況下，使用大整數庫或使用 2*32 位變數計算或尋找 32 位modmul實作。
uj5u.com熱心網友回復：
該運算式暗示使用浮點型別。因此，使用函式fmod來獲得除法的余數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/363818.html