結果
問題 | No.665 Bernoulli Bernoulli |
ユーザー | MtSaka |
提出日時 | 2021-08-31 01:54:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 4,889 bytes |
コンパイル時間 | 1,913 ms |
コンパイル使用メモリ | 205,976 KB |
実行使用メモリ | 8,308 KB |
最終ジャッジ日時 | 2024-05-03 13:06:52 |
合計ジャッジ時間 | 2,953 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
8,064 KB |
testcase_01 | AC | 7 ms
7,888 KB |
testcase_02 | AC | 8 ms
7,936 KB |
testcase_03 | AC | 7 ms
8,136 KB |
testcase_04 | AC | 7 ms
8,064 KB |
testcase_05 | AC | 8 ms
8,192 KB |
testcase_06 | AC | 8 ms
8,064 KB |
testcase_07 | AC | 8 ms
8,064 KB |
testcase_08 | AC | 8 ms
8,064 KB |
testcase_09 | AC | 7 ms
8,180 KB |
testcase_10 | AC | 8 ms
8,120 KB |
testcase_11 | AC | 9 ms
8,192 KB |
testcase_12 | AC | 8 ms
8,200 KB |
testcase_13 | AC | 9 ms
8,192 KB |
testcase_14 | AC | 8 ms
8,192 KB |
testcase_15 | AC | 8 ms
8,308 KB |
testcase_16 | AC | 8 ms
8,192 KB |
testcase_17 | AC | 7 ms
8,064 KB |
testcase_18 | AC | 8 ms
8,064 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);} template<long long m> struct modint{ long long x; modint():x(0){} modint(long long y):x(y>=0?y%m:(m-(-y)%m)%m){} modint inv()const{long long a=x,b=m,u=1,v=0,t; while(b){ t=a/b; swap(a-=t*b,b); swap(u-=t*v,v); } return modint(u); } modint &operator+=(const modint&p) {if((x+=p.x)>=m)x-=m;return *this;} modint &operator-=(const modint&p){if((x+=m-p.x)>=m)x-=m;return *this;} modint &operator*=(const modint&p) {x=x*p.x%m;return *this;} modint &operator/=(const modint&p){*this*=p.inv();return *this;} modint operator-()const{return modint(-x); } modint operator+(const modint&p)const{return modint(*this)+=p; } modint operator-(const modint&p)const{return modint(*this)-=p; } modint operator*(const modint&p)const{return modint(*this)*=p; } modint operator/(const modint&p)const{return modint(*this)/=p; } bool operator==(const modint&p)const{return x==p.x;} bool operator!=(const modint&p)const{return x!=p.x;} modint pow(long long n) const { modint ret(1),mul(x); while(n){ if(n&1)ret*=mul; mul*=mul; n>>=1; } return ret; } friend ostream &operator<<(ostream &os,const modint&p) { return os<<p.x; } friend istream &operator>>(istream &is, modint &a) { long long t; is>>t; a=modint<m>(t); return (is); } static long long get_mod(){return m;} }; template<long long m> struct combination{ using mint=modint<m>; vector<mint>dat,idat; long long mx; combination(long long mx_=300000):dat(mx_+1,1),idat(mx_+1,1),mx(mx_){ for(long long i=1;i<=mx;i++)dat[i]=dat[i-1]*mint(i); idat[mx]/=dat[mx]; for(long long i=mx;i>0;i--)idat[i-1]=idat[i]*mint(i); } mint com(long long n,long long k){ if(n<0||k<0||n<k)return mint(0); return dat[n]*idat[k]*idat[n-k]; } mint fac(long long n){ if(n<0)return mint(0); return dat[n]; } }; template<long long m> modint<m> lagrange_polynominal(vector<modint<m>>&y,long long t){ using mint=modint<m>; long long n=y.size()-1; combination<m>c; if(t<=n)return y[t]; mint ret; vector<mint>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++){ mint tmp=y[i]*dp[i]*pd[i]*c.idat[i]*c.idat[n-i]; if((n-i)&1)ret-=tmp; else ret+=tmp; } return ret; } using mint=modint<MOD>; int main(){ LL(n,k); vector<mint>v(k+2); rep(i,1,k+2){ v[i]=v[i-1]+mint(i).pow(k); } fin(lagrange_polynominal(v,n)); }