結果
| 問題 | No.503 配列コレクション |
| ユーザー |
 n_vip
|
| 提出日時 | 2017-04-07 23:12:57 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,052 bytes |
| コンパイル時間 | 942 ms |
| コンパイル使用メモリ | 108,412 KB |
| 実行使用メモリ | 503,484 KB |
| 最終ジャッジ日時 | 2024-07-16 02:59:16 |
| 合計ジャッジ時間 | 35,734 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 12 WA * 7 TLE * 1 -- * 5 |
ソースコード
#include <string>#include <vector>#include<iostream>#include<cstdio>#include<cstdlib>#include<stack>#include<queue>#include<cmath>#include<algorithm>#include<functional>#include<list>#include<deque>#include<bitset>#include<set>#include<map>#include<unordered_map>#include<unordered_set>#include<cstring>#include<sstream>#include<complex>#include<iomanip>#include<numeric>#include<cassert>#define X first#define Y second#define pb push_back#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))#define peat(X,Y) for (;(X) < (Y);++(X))#define all(X) (X).begin(),(X).end()#define rall(X) (X).rbegin(),(X).rend()#define eb emplace_back#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())#define Endl endlusing namespace std;typedef long long ll;typedef pair<int,int> pii;typedef pair<ll,ll> pll;template<class T> using vv=vector<vector<T>>;template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}#define out(args...){vector<string> a_r_g_s=s_p_l_i_t(#args, ','); e_r_r(a_r_g_s.begin(), args); }vector<string> s_p_l_i_t(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while(getline(ss,x,c)) v.emplace_back(x); returnmove(v);}void e_r_r(vector<string>::iterator it) {}template<typename T, typename... Args> void e_r_r(vector<string>::iterator it, T a, Args... args){ if(*it==" 1"||*it=="1") cerr<<endl; else cerr <<it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; e_r_r(++it, args...);}const ll MOD=1e9+7;ll modpow(ll r,ll n,ll m=MOD){ll re=1,d=r%m;if(n<0)(n%=m-1)+=m-1;for(;n;n/=2){if(n&1)(re*=d)%=m;(d*=d)%=m;}return re;}template <int mod=MOD> struct modInt{int v;modInt(int v=0):v(v){}modInt operator+(const modInt &n){return v+n.v<mod ? v+n.v : v+n.v-mod;}modInt operator-(const modInt &n){return v-n.v<0 ? v-n.v+mod : v-n.v;}modInt operator*(const modInt &n){return ll(v)*n.v%mod;}modInt operator/(const modInt &n){return ll(v)*modpow(n.v%mod,-1,mod)%mod;}template<class T> modInt operator+(const T &n){return v+n<mod ? v+n : v+n-mod;}template<class T> modInt operator-(const T &n){return v-n<0 ? v-n+mod : v-n;}template<class T> modInt operator*(const T &n){return ll(v)*(n%mod)%mod;}template<class T> modInt operator/(const T &n){return ll(v)*modpow(n%mod,-1,mod)%mod;}modInt& operator+=(const modInt &n){v+=n.v; if(v>=mod) v-=mod; return *this;}modInt& operator-=(const modInt &n){v-=n.v; if(v<0) v+=mod; return *this;}modInt& operator*=(const modInt &n){v=ll(v)*n.v%mod; return *this;}modInt& operator/=(const modInt &n){v=ll(v)*modpow(n.v,-1,mod)%mod; return *this;}template<class T> modInt& operator+=(const T &n){v+=n; if(v>=mod) v-=mod; return *this;}template<class T> modInt& operator-=(const T &n){v-=n; if(v<0) v+=mod; return *this;}template<class T> modInt& operator*=(const T &n){v=ll(v)*n%mod; return *this;}template<class T> modInt& operator/=(const T &n){v=ll(v)*modpow(n,-1,mod)%mod; return *this;}};template<int mod> ostream& operator<<(ostream &os,const modInt<mod> &n){return os<<n.v;};template<class T,int mod> modInt<mod> operator+(const T &n,const modInt<mod> &m){return m.v+n<mod ? m.v+n : m.v+n-mod;}template<class T,int mod> modInt<mod> operator-(const T &n,const modInt<mod> &m){return n-m.v<0 ? n-m.v+mod : n-m.v;}template<class T,int mod> modInt<mod> operator*(const T &n,const modInt<mod> &m){return ll(m.v)*(n%mod)%mod;}template<class T,int mod> modInt<mod> operator/(const T &n,const modInt<mod> &m){return ll(m.v)*modpow(n%mod,-1,mod)%mod;}typedef modInt<MOD> mint;template <int mod> modInt<mod> modpow(modInt<mod> r,ll n){ mint re(1); if(n<0)(n%=mod-1)+=mod-1; for(;n;n/=2){if(n&1) re*=r; r*=r;} return re;}vector<mint> fact,finv,inv;mint comb(ll n,ll r){ if(n<r||r<0)return 0; return fact[n]*finv[n-r]*finv[r];}class Doralion{void Modinvs(vector<mint> &re,int n){ re.resize(n+1); re[1]=1; for(int i=2;i<=n;++i)re[i]=re[MOD%i]*(MOD-MOD/i);}void Facts(vector<mint> &re,int n){ re.resize(n+1); re[0]=1; rep(i,n)re[i+1]=re[i]*(i+1);}void Factinvs(vector<mint> &re,const vector<mint> &inv,int n){ re.resize(n+1); re[0]=1; rep(i,n)re[i+1]=re[i]*inv[i+1];}public:Doralion(int n){ Modinvs(inv,n); Facts(fact,n); Factinvs(finv,inv,n);}} doralion(212345);vector<ll> fact_,finv_,inv_;ll comb_(ll n,ll r){if(n<r||r<0)return 0;return fact_[n]*finv_[n-r]%MOD*finv_[r]%MOD;}class Doralion_{void Modinvs(vector<ll> &re,int n){re.resize(n+1); re[1]=1;for(int i=2;i<=n;++i)re[i]=re[MOD%i]*(MOD-MOD/i)%MOD;}void Facts(vector<ll> &re,int n){re.resize(n+1); re[0]=1;rep(i,n)re[i+1]=re[i]*(i+1)%MOD;}void Factinvs(vector<ll> &re,const vector<ll> &inv_,int n){re.resize(n+1); re[0]=1;rep(i,n)re[i+1]=re[i]*inv_[i+1]%MOD;}public:Doralion_(int n){Modinvs(inv_,n);Facts(fact_,n);Factinvs(finv_,inv_,n);}} doralion_(21234567);int main(){ios_base::sync_with_stdio(false);cout<<fixed<<setprecision(0);int n,k,d;cin>>n>>k>>d;int t=(n-k)/(k-1)+1;int l=n-t*(k-1);if(d==1){cout<<l<<endl;return 0;}mint p=1,re=0,c=1;rep(i,t) p*=d;rrep(i,t+1){if(i<t){c*=l-2+t-i;c*=inv[t-i];}re+=p*c;//out(p,re,l-2+t-i,t-i,1);p*=inv[d];}cout<<re*l<<endl;// vector<mint> dp(t+1);// dp[t]=1;// rep(i,l){// vector<mint> nxt(t+1);// rrep(j,t+1){// rep(k,j,t+1) nxt[j]+=dp[k]// }// cout<<nxt;// swap(dp,nxt);// }// cout<<dp[0]<<endl;return 0;}