結果
問題 | No.2120 場合の数の下8桁 |
ユーザー | leaf_1415 |
提出日時 | 2022-11-04 21:43:35 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 744 ms / 2,000 ms |
コード長 | 3,812 bytes |
コンパイル時間 | 838 ms |
コンパイル使用メモリ | 102,708 KB |
実行使用メモリ | 160,128 KB |
最終ジャッジ日時 | 2024-07-18 19:27:22 |
合計ジャッジ時間 | 16,920 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 726 ms
159,872 KB |
testcase_01 | AC | 735 ms
160,000 KB |
testcase_02 | AC | 734 ms
159,872 KB |
testcase_03 | AC | 739 ms
160,000 KB |
testcase_04 | AC | 730 ms
160,000 KB |
testcase_05 | AC | 734 ms
160,000 KB |
testcase_06 | AC | 719 ms
159,872 KB |
testcase_07 | AC | 731 ms
160,128 KB |
testcase_08 | AC | 727 ms
160,000 KB |
testcase_09 | AC | 730 ms
160,000 KB |
testcase_10 | AC | 742 ms
160,000 KB |
testcase_11 | AC | 735 ms
159,872 KB |
testcase_12 | AC | 725 ms
160,000 KB |
testcase_13 | AC | 739 ms
160,000 KB |
testcase_14 | AC | 741 ms
160,000 KB |
testcase_15 | AC | 741 ms
160,000 KB |
testcase_16 | AC | 744 ms
160,000 KB |
testcase_17 | AC | 728 ms
159,744 KB |
testcase_18 | AC | 743 ms
160,000 KB |
testcase_19 | AC | 732 ms
160,000 KB |
ソースコード
#include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <ctime> #include <cstdlib> #include <cassert> #include <vector> #include <list> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <string> #include <algorithm> #include <utility> #include <complex> #include <array> #include <unordered_set> #include <unordered_map> #define rep(x, s, t) for(ll x = (s); (x) <= (t); (x)++) #define per(x, s, t) for(ll x = (s); (x) >= (t); (x)--) #define reps(x, s) for(ll x = 0; (x) < (ll)(s).size(); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define sz(x) ((ll)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define outl(...) dump_func(__VA_ARGS__) #define outf(x) cout << fixed << setprecision(16) << (x) << endl #define pb push_back #define fi first #define se second #define inf 2e18 #define eps 1e-9 const double PI = 3.1415926535897932384626433; using namespace std; typedef long long ll; typedef pair<int, int> P; map<ll, ll> mp; ll a[55], b[55], m[55]; bool prime[100005]; ll gcd(ll a, ll b){ if(b == 0) return a; return gcd(b, a%b); } //ax+by = gcd(a, b)を満たす(x, y)を求めgcd(a, b)を返す ll extgcd(ll a, ll b, ll &x, ll &y) { if(b == 0){ x = 1, y = 0; return a; } ll xx, yy; ll d = extgcd(b, a%b, xx, yy); x = yy, y = xx-(a/b)*yy; return d; } //a^{-1} (mod m)を求める。存在しない場合(gcd(a, m)!=1)は-1を返す ll mod_inverse(ll a, ll m) { ll x, y; if(extgcd(a, m, x, y) != 1) return -1; return (x%m + m) % m; } //ax = b (mod m)を満たすx(mod m/gcd(a, m))を求める。存在しない場合(b%gcd(a, m)!=0)は(0, -1)を返す P congruence(ll a, ll b, ll m) { ll d = gcd(a, m); if(b % d) return make_pair(0, -1); a /= d, b /= d, m /= d; return make_pair(b * mod_inverse(a, m) % m, m); } //連立合同方程式a_i*x = b_i (mod m_i)(i = 1, 2, ..., n)の解(x, M)を求める。存在しない場合(0, -1)を返す P SimultaneousCongruence(ll a[], ll b[], ll m[], ll n) { ll x = 0, M = 1; for(int i = 1; i <= n; i++){ P res = congruence(a[i]*M, (b[i]-a[i]*x%m[i]+m[i])%m[i], m[i]); if(res.second == -1) return res; x += M*res.first, M *= res.second; } return make_pair(x, M); } const int FACT_MAX = 10000005; ll q[FACT_MAX], e[FACT_MAX]; ll modpow(ll a, ll n, ll mod) { if(n == 0) return 1; if(n % 2){ return ((a%mod) * (modpow(a, n-1, mod)%mod)) % mod; } else{ return modpow((a*a)%mod, n/2, mod) % mod; } } void make_fact(ll p, ll mod) { ll qval = 1, eval = 0; q[0] = 1, e[0] = 0; for(int i = 1; i < FACT_MAX; i++){ ll t = i; while(t % p == 0){ eval++; t /= p; } qval *= t, qval %= mod; q[i] = qval, e[i] = eval; } } ll comb(ll n, ll k, ll p, ll ex, ll mod) { if(n < 0 || k < 0 || n < k) return 0; ll eval = e[n] - e[k] - e[n-k]; if(eval >= ex) return 0; ll ret = q[n] * mod_inverse(q[k]*q[n-k]%mod, mod) % mod; ret *= modpow(p, eval, mod), ret %= mod; return ret; } ll n, k; ll calc(ll p, ll ex, ll mod) { make_fact(p, mod); //mod = p^exのときの答えを求める処理を書く return comb(n, k, p, ex, mod); } //Mを法とする int main(void) { cin >> n >> k; ll M = 100000000; for(int i = 2; i < 100005; i++){ if(prime[i]) continue; for(int j = 2*i; j < 100005; j+=i) prime[j] = true; } for(int i = 2; i < 100005; i++){ if(prime[i]) continue; while(M%i == 0){ mp[i]++; M /= i; } } if(M > 1) mp[M]++; ll id = 0; for(auto it = mp.begin(); it != mp.end(); it++){ id++; ll mod = 1; for(int i = 0; i < it->second; i++) mod *= it->first; a[id] = 1, b[id] = calc(it->first, it->second, mod), m[id] = mod; } printf("%08d\n", (int)SimultaneousCongruence(a, b, m, id).first); return 0; }