結果
問題 | No.129 お年玉(2) |
ユーザー |
![]() |
提出日時 | 2020-04-28 00:04:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 5,000 ms |
コード長 | 1,197 bytes |
コンパイル時間 | 1,114 ms |
コンパイル使用メモリ | 101,724 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-22 16:18:00 |
合計ジャッジ時間 | 3,101 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
// I SELL YOU...! #include<iostream> #include<vector> #include<algorithm> #include<functional> #include<queue> #include<chrono> #include<iomanip> #include<map> #include<set> using namespace std; using ll = long long; using P = pair<ll,ll>; using TP = tuple<ll,ll,ll>; void init_io(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } #define MOD 1000000000 map<ll,ll> dv(ll n){ map<ll,ll> mp; for(ll i=2;i*i<=n;i++){ ll cnt = 0; while(n%i==0){ n/=i; cnt++; } if(cnt>0){ mp[i]+=cnt; } } if(n!=1) mp[n]++; return mp; } long long pmod(long long x, long long n) { if(n==0) return 1; if(n%2==0){ ll v = pmod(x,n/2); v*=v; v %= MOD; return v; } return (x*pmod(x,n-1))%MOD; } ll cmb(ll n,ll r){ map<ll,ll> mp; ll res=1; for(ll i=1;i<=r;i++){ map<ll,ll> t0=dv(n+1-i),t1=dv(i); for(auto p:t0){ mp[p.first]+=p.second; } for(auto p:t1){ mp[p.first]-=p.second; } } for(auto p:mp){ res *= pmod(p.first,p.second); res %= MOD; } return res; } signed main(){ init_io(); ll n,m; cin >> n >> m; n /= 1000; n -= (n/m)*m; cout << cmb(m,n)<<endl; }