Korean, Edit

C 言語の二項係数

上位カテゴリ : 【C言語】 C言語索引

a. GitHub

1.の上）

それが良い問題である場合、データ型のサイズ制限のため、この方法は使用できません。

「」c #include #include 二重 x = 1; int i = 0; int n、r;

void a(){ if(i < r){ x *= (倍精度) (n - i) / (倍精度) (r - i); 私は++; a(); } }

int main(int argc, char *argv[]) { scanf(“%d %d”, &n, &r); a(); printf(“%.lf”, x); 0を返します。 } 「」

2. O(n²)

この方法は暗記と呼ばれ、記憶力によって制限されます。

「」c #include #include #define Max 1000 // 'r' の最大値 // n C r = n-1 C r-1 + n-1 C r に注意してください。

long long int min(long long int a, long long int b){ if(a < b) a を返します。 それ以外の場合は b を返します。 }

int main(int argc, char *argv[]) { long long int n、r、i、j; scanf(“%lld %lld”, &n, &r); r = min(r, n - r); // 最適化のため Long Long int C[Max + 1][2] = { {0, }, }; C[0][0] = 1; for(i = 1; i <= n; i ++){ C[0][1] = 1; for(j = 1; j <= min(i, r); j ++) C[j][1] = C[j-1][0] + C[j][0]; // C[j][0] = i-1 C j および C[j][1] = i C j for(j = 0; j <= min(i, r); j ++) C[j][0] = C[j][1]; } printf(“%d”, C[r][0]); 0を返します。 } 「」

3.の上）

_nC_r (mod p) の計算方法について説明します。

「」c #include #include #define p 1999 // 'p' は 'p'rime #define g(p) 3 // g( ): 原始ルート

int main(int argc, char *argv[]) { int notepad = 1、指数セット[p]、残りセット[p]; // 0 ~ p-1 (mod p) long long int n、r、i、j; int 指数_I = 0; // ん！ ÷ (n - r)! ≡ (g(p)) 指数_I (mod p) int 指数 II = 0; // r! ≡(g(p)) 指数_II (mod p)

for(i = 0; i < p - 1; i ++){ // (g(p)) p - 1

≡1 (mod p) (フェルマーの小定理) (①) 指数セット[メモ帳] = i; // 余り → g(p) の指数 残りセット[i] = メモ帳; // g(p) の指数 → 余り メモ帳 *= g(p);メモ帳 %= p; } scanf(“%lld %lld”, &n, &r); メモ帳 = 0; for(i = n; i > n - r; i –){ j = i; while(1){ if(j % p != 0) ブレーク; メモ帳++; j /= p; } exponent_I += exponent_set[j % p]; 指数_I %= p - 1; // (①) } for(i = r; i > 0; i –){ j = i; while(1){ if(j % p != 0) ブレーク; メモ帳 –; j /= p; } exponent_II += exponent_set[j % p]; 指数 II %= p - 1; // (①) }

// n C r ≡ (g(p)) exponent_I - exponent_II (mod p) if(メモ帳 > 0) printf(“0”); // メモ帳は常に -1 を超えます それ以外 { if(指数_I < 指数_II) 指数_II -= p - 1; // (①) printf(“%d”, 剰余_セット[指数_I - 指数_II]); } 0を返します。 } 「」

入力: 2016.03.01 13:55