結果
問題 | No.503 配列コレクション |
ユーザー |
|
提出日時 | 2017-04-07 23:35:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 3,251 bytes |
コンパイル時間 | 1,510 ms |
コンパイル使用メモリ | 170,168 KB |
実行使用メモリ | 7,192 KB |
最終ジャッジ日時 | 2024-07-16 03:15:06 |
合計ジャッジ時間 | 2,341 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define mt make_tuple#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()#define pb push_backtypedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<ll> vll;template<int MOD>class ModInt {public:ModInt() :value(0) {}ModInt(long long val) :value((int)(val<0 ? MOD + val%MOD : val%MOD)) { }ModInt& operator+=(ModInt that) {value = value + that.value;if (value >= MOD)value -= MOD;return *this;}ModInt& operator-=(ModInt that) {value -= that.value;if (value<0)value += MOD;return *this;}ModInt& operator*=(ModInt that) {value = (int)((long long)value * that.value % MOD);return *this;}ModInt &operator/=(ModInt that) {return *this *= that.inverse();}ModInt operator+(ModInt that) const {return ModInt(*this) += that;}ModInt operator-(ModInt that) const {return ModInt(*this) -= that;}ModInt operator*(ModInt that) const {return ModInt(*this) *= that;}ModInt operator/(ModInt that) const {return ModInt(*this) /= that;}ModInt pow(long long k) const {if (value == 0)return 0;ModInt n = *this, res = 1;while (k) {if (k & 1)res *= n;n *= n;k >>= 1;}return res;}ModInt inverse() const {long long a = value, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}return ModInt(u);}int toi() const { return value; }private:int value;};typedef ModInt<1000000007> mint;ostream& operator<<(ostream& os, const mint& x) {os << x.toi();return os;}mint nPr(int n, int r, const vector<mint> &fact) {return fact[n] / fact[n - r];}mint nCr(int n, int r, const vector<mint> &fact) {if (r > n)return 0;return fact[n] / (fact[r] * fact[n - r]);}mint nHr(int n, int r, const vector<mint> &fact) {return nCr(n + r - 1, r, fact);}/*r-1+k-1<kr-2<0r<2*/int main(){ios::sync_with_stdio(false);cin.tie(0);int N, K, D;cin >> N >> K >> D;vector<mint> fact(N + 1, 1);rep(i, N)fact[i + 1] = fact[i] * (i + 1);int m = 0, r = N;while (r >= K) {r -= K - 1;m++;}if (D == 1) {// {1,1,1,...,1}cout << r << endl;return 0;}if (r == 1) {mint ans = 1;rep(i, m)ans *= D;cout << ans << endl;return 0;}mint ans = 0, pw = 1;for (int i = 0; i <= m; ++i) {int k = m - i;if (!(r - 1 == 0 && k > 0)) {ans += nHr(r - 1, k, fact)*pw*r;}pw *= D;}cout << ans << endl;}