結果
問題 | No.645 Count Permutation |
ユーザー | Pulmn |
提出日時 | 2017-08-23 21:15:26 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 797 bytes |
コンパイル時間 | 710 ms |
コンパイル使用メモリ | 62,852 KB |
実行使用メモリ | 11,424 KB |
最終ジャッジ日時 | 2024-04-23 13:16:37 |
合計ジャッジ時間 | 6,858 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
11,292 KB |
testcase_01 | AC | 3 ms
6,940 KB |
testcase_02 | AC | 568 ms
6,940 KB |
testcase_03 | AC | 38 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 7 ms
6,940 KB |
testcase_07 | AC | 20 ms
6,944 KB |
testcase_08 | AC | 23 ms
6,940 KB |
testcase_09 | AC | 1,868 ms
6,940 KB |
testcase_10 | AC | 57 ms
6,944 KB |
testcase_11 | TLE | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
ソースコード
#include <iostream> #include <vector> using namespace std; typedef long long ll; typedef vector<ll> vl; const ll mod=1e9+7; ll Pow_mod(ll n,ll p){ ll r=1; for(;p>0;p>>=1){ if(p&1) r=(r*n)%mod; n=(n*n)%mod; } return r; } vl fact(100005); ll Fact(ll n){ if(fact[n]) return fact[n]; if(!n) return fact[n]=1; return fact[n]=Fact(n-1)*n%mod; } ll Div(ll n,ll m){ return n*Pow_mod(m,mod-2)%mod; } ll nPk(ll n,ll k){ return Div(Fact(n),Fact(n-k)); } ll n,l,r; int main(){ cin>>n>>l>>r; vl dp(n); dp[0]=1; ll x=2,res=0; if(!l){ res=n-1; for(int i=1;i<n;i++) (res*=i)%=mod; } while(x<=r){ vl DP(n+1); for(int i=1;i<n;i++){ for(int j=0;j<i;j++){ (DP[i]+=dp[j]*nPk(n-j-2,i-j-1))%=mod; } } dp=DP; if(l<=x) (res+=dp[n-1])%=mod; x*=2; } cout<<res<<endl; }