結果
問題 | No.2120 場合の数の下8桁 |
ユーザー | chro_96 |
提出日時 | 2022-11-04 22:39:53 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 284 ms / 2,000 ms |
コード長 | 1,844 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 31,744 KB |
実行使用メモリ | 40,960 KB |
最終ジャッジ日時 | 2024-07-18 20:35:40 |
合計ジャッジ時間 | 2,122 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <stdio.h>long long gcd (long long a, long long b, long long *x, long long *y) {long long ans = 0LL;if (a <= 0LL || b <= 0LL) {return 0LL;}if (a%b == 0LL) {*x = 0LL;*y = 1LL;return b;}ans = gcd(b, a%b, y, x);*y -= (a/b)*(*x);return ans;}int main () {int m = 0;int n = 0;int res = 0;long long ans = 1LL;long long inv[5000001] = {};int cnt2 = 0;int cnt5 = 0;int pow2 = 2;int pow5 = 5;long long mod_num = 100000000LL;res = scanf("%d", &m);res = scanf("%d", &n);if (m < n) {printf("00000000\n");return 0;}if (m-n < n) {n = m-n;}while (pow2 <= m) {cnt2 += m/pow2-(m-n)/pow2;cnt2 -= n/pow2;pow2 *= 2;}while (pow5 <= m) {cnt5 += m/pow5-(m-n)/pow5;cnt5 -= n/pow5;pow5 *= 5;}inv[1] = 1LL;for (int i = 2; i <= n; i++) {if (inv[i] <= 0LL) {if (i%2LL == 0LL) {inv[i] = inv[i/2LL];} else if (i%5LL == 0LL) {inv[i] = inv[i/5LL];} else {long long x = 0LL;long long y = 0LL;long long d = gcd(mod_num, (long long)i, &x, &y);if (y <= 0LL) {y += (1+(-y)/mod_num)*mod_num;}inv[i] = y%mod_num;}for (int p = 2; i*p <= n; p++) {inv[p*i] = (inv[p]*inv[i])%mod_num;}}}for (int i = 0; i < n; i++) {long long tmp = (long long) (m-i);while (tmp%2LL == 0LL) {tmp /= 2LL;}while (tmp%5LL == 0LL) {tmp /= 5LL;}ans *= tmp;ans %= mod_num;ans *= inv[i+1];ans %= mod_num;}while (cnt2 > 0) {ans = (ans*2LL)%mod_num;cnt2--;}while (cnt5 > 0) {ans = (ans*5LL)%mod_num;cnt5--;}printf("%08lld\n", ans);return 0;}