結果
問題 | No.665 Bernoulli Bernoulli |
ユーザー | MtSaka |
提出日時 | 2021-08-30 22:15:20 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 4,059 bytes |
コンパイル時間 | 4,027 ms |
コンパイル使用メモリ | 265,456 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-03 08:15:14 |
合計ジャッジ時間 | 5,082 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 3 ms
5,376 KB |
ソースコード
//GIVE ME AC!!!!!!!!!!!!!!!!! //#pragma GCC target("avx") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define ll long long #define ld long double #define floatset() fixed<<setprecision(15) #define all(n) n.begin(),n.end() #define rall(n) n.rbegin(),n.rend() #define rep(i, s, n) for (ll i = s; i < (ll)(n); i++) #define pb push_back #define eb emplace_back #define max_(a) *max_element(all(a)) #define min_(a) *min_element(all(a)) #define INT(...) int __VA_ARGS__;scan(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__) using namespace std; using vl=vector<ll>; using vi=vector<int>; using vs=vector<string>; using vc=vector<char>; using vvl=vector<vl>; using P=pair<ll,ll>; using vvc=vector<vc>; using vd=vector<double>; using vp=vector<P>; using vb=vector<bool>; const int dx[8]={1,0,-1,0,1,-1,-1,1}; const int dy[8]={0,1,0,-1,1,1,-1,-1}; const ll inf=2e18; const ll MOD=1000000007; const ll mod=998244353; const double pi=acos(-1); template<typename T1,typename T2 > ostream &operator<<(ostream&os,const pair<T1,T2>&p) { os<<p.first<<" "<<p.second; return os; } template<typename T1,typename T2> istream &operator>>(istream&is,pair<T1,T2>&p) { is>>p.first>>p.second; return is; } template<typename T> ostream &operator<<(ostream&os,const vector<T>&v) { for(int i=0;i<(int)v.size();i++) { os<<v[i]<<(i+1!=v.size()?" ":""); } return os; } template<typename T> istream &operator>>(istream&is,vector<T>&v) { for(T &in:v)is>>in; return is; } void scan(){} template<class Head,class... Tail> void scan(Head&head,Tail&... tail) { cin>>head; scan(tail...); } template<class T> void print(const T &t) { cout << t << '\n'; } template<class Head, class... Tail> void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } template<class... T> void fin(const T &... a) { print(a...); exit(0); } template<typename T> ll sum_(vector<T>&v){ ll res=0; for(auto &e:v)res+=e; return res; } template<typename T1,typename T2> inline bool chmax(T1&a,T2 b){return a<b&&(a=b,true);} template<typename T1,typename T2> inline bool chmin(T1&a,T2 b){return a>b&&(a=b,true);} #if __has_include(<atcoder/all>) #include <atcoder/all> using mint = atcoder::modint1000000007; #endif template< typename T > struct Combination { vector< T > _fact, _rfact; Combination(int sz) : _fact(sz + 1), _rfact(sz + 1) { _fact[0] = _rfact[sz] = 1; for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i; _rfact[sz] /= _fact[sz]; for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1); } inline T fact(int k) const { return _fact[k]; } inline T rfact(int k) const { return _rfact[k]; } T P(int n, int r) const { if(r < 0 || n < r) return 0; return fact(n) * rfact(n - r); } T C(int p, int q) const { if(q < 0 || p < q) return 0; return fact(p) * rfact(q) * rfact(p - q); } T H(int n, int r) const { if(n < 0 || r < 0) return (0); return r == 0 ? 1 : C(n + r - 1, r); } }; template< typename T > T lagrange_polynomial(const vector< T > &y, int64_t t) { int N=y.size()-1; Combination<T>comb(N); if(t<=N) return y[t]; T ret(0); vector< T > dp(N + 1, 1), pd(N + 1, 1); for(int i = 0; i < N; i++) dp[i + 1] = dp[i] * (t - i); for(int i = N; i > 0; i--) pd[i - 1] = pd[i] * (t - i); for(int i = 0; i <= N; i++) { T tmp = y[i] * dp[i] * pd[i] * comb.rfact(i) * comb.rfact(N - i); if((N - i) & 1) ret -= tmp; else ret += tmp; } return ret; } long long modpow(long long a,long long n,long long m){ long long ans=1; while(n>0){ if(n&1)ans=ans*a%m; a=a*a%m; n>>=1; } return ans; } int main(){ LL(n,k); vector<mint>y(k+2); rep(i,1,k+2){ y[i]=y[i-1]; y[i]+=modpow(i,k,MOD); } cout<<lagrange_polynomial(y,n).val()<<endl; }