結果
問題 | No.503 配列コレクション |
ユーザー |
|
提出日時 | 2017-04-07 23:09:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 2,811 bytes |
コンパイル時間 | 897 ms |
コンパイル使用メモリ | 106,536 KB |
実行使用メモリ | 10,972 KB |
最終ジャッジ日時 | 2024-07-16 02:57:24 |
合計ジャッジ時間 | 1,859 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>#include <iterator>using namespace std;// a,b の最大公約数と、ax + by = gcd(a,b) となる x,y を求めるlong long extgcd(long long a, long long b, long long &x, long long &y) {long long g = a;if(b != 0){g = extgcd(b, a % b, y, x);y -= (a / b) * x;}else{x = 1;y = 0;}return g;}// ax ≡ gcd(a, m) (mod m) となる x を求める// a, m が互いに素ならば、関数値は mod m での a の逆数となるlong long mod_inverse(long long a, long long m){long long x, y;extgcd(a, m, x, y);return (x % m + m) % m;}// 階乗数の事前計算を用いた各種組合せclass FactorialCalculation{private:const int mod;vector<long long> factorial;vector<long long> invFactorial;public:FactorialCalculation(int n, int mod) : mod(mod){factorial.resize(n+1, 1);invFactorial.resize(n+1, 1);for(int i=1; i<=n; ++i){factorial[i] = factorial[i-1] * i % mod;invFactorial[i] = mod_inverse(factorial[i], mod);}}long long getFactorial(int n){return factorial[n];}long long getPermutation(int n, int r){if(n < r)return 0;return factorial[n] * invFactorial[n-r] % mod;}long long getCombination(int n, int r){if(n < r)return 0;return getPermutation(n, r) * invFactorial[r] % mod;}long long getHomogeneous(int n, int r){return getCombination(n+r-1, r);}};const int MOD = 1000000007;// 累乗、べき乗long long power(int a, int b){long long ret = 1;long long tmp = a;while(b > 0){if(b & 1){ret *= tmp;ret %= MOD;}tmp *= tmp;tmp %= MOD;b >>= 1;}return ret;}int main(){int n, k, d;cin >> n >> k >> d;int cnt = (n - 1) / (k - 1);int len = n - cnt * (k - 1);if(d == 1){cout << len << endl;return 0;}if(len == 1){cout << power(d, cnt) << endl;return 0;}FactorialCalculation calc(len+cnt, MOD);long long ans = 0;for(int i=0; i<=cnt; ++i){ans += power(d, i) * calc.getHomogeneous(len - 1, cnt - i);ans %= MOD;}ans *= len;ans %= MOD;cout << ans << endl;return 0;}