結果
問題 | No.503 配列コレクション |
ユーザー |
![]() |
提出日時 | 2017-02-17 11:38:39 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 1,565 bytes |
コンパイル時間 | 899 ms |
コンパイル使用メモリ | 89,748 KB |
実行使用メモリ | 57,808 KB |
最終ジャッジ日時 | 2024-12-30 22:45:34 |
合計ジャッジ時間 | 2,204 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include <iostream>#include <fstream>#include <typeinfo>#include <vector>#include <stack>#include <cmath>#include <set>#include <map>#include <string>#include <algorithm>#include <cstdio>#include <queue>#include <iomanip>#include <cctype>#define syosu(x) fixed<<setprecision(x)using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> P;typedef pair<double,double> pdd;typedef pair<ll,ll> pll;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<double> vd;typedef vector<vd> vvd;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<char> vc;typedef vector<vc> vvc;typedef vector<string> vs;typedef vector<bool> vb;typedef vector<vb> vvb;typedef vector<P> vp;typedef vector<vp> vvp;typedef vector<pll> vpll;typedef pair<int,P> pip;typedef vector<pip> vip;const int inf=1<<30;const ll INF=1ll<<52;const double pi=acos(-1);const double eps=1e-8;const ll mod=1e9+7;const vi emp;const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};const int DX[8]={-1,-1,-1,0,0,1,1,1},DY[8]={1,0,-1,1,-1,1,0,-1};ll n,k,d;int main(){cin>>n>>k>>d;// a:=残り数 b:=処理数ll a=n%(k-1)==0?k-1:n%(k-1),b=(n-a)/(k-1);// コーナーケースif(d==1){cout<<a<<endl;return 0;}// dp:=通り数 DP:=総和vvl dp(a+1,vl(b+1)),DP(a+1,vl(b+1));dp[0][0]=1;for(int i=1;i<=a;i++){ll x=0,y=0,z=0;for(int j=0;j<=b;j++){x=(x+dp[i-1][j])%mod;y=(y+DP[i-1][j])%mod;z=(z*d+dp[i-1][j])%mod;dp[i][j]=x;DP[i][j]=(y+z)%mod;}}cout<<DP[a][b]<<endl;}