結果
| 問題 | No.665 Bernoulli Bernoulli |
| ユーザー |
 WA_TLE
|
| 提出日時 | 2018-03-09 23:50:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 959 ms / 2,000 ms |
| コード長 | 5,231 bytes |
| コンパイル時間 | 1,272 ms |
| コンパイル使用メモリ | 128,548 KB |
| 最終ジャッジ日時 | 2025-01-05 09:11:48 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 15 |
ソースコード
#include<deque>#include<queue>#include<vector>#include<algorithm>#include<iostream>#include<set>#include<cmath>#include<tuple>#include<string>#include<chrono>#include<functional>#include<iterator>#include<random>#include<unordered_set>#include<unordered_map>#include<array>#include<map>#include<bitset>#include<iomanip>#include<list>#include <numeric>using namespace std;typedef unsigned long long int ulint;typedef long long int llint;typedef long double lldo;#define mp make_pair#define mt make_tuple#define pub push_back#define puf push_front#define pob pop_back#define pof pop_front#define fir first#define sec second#define res resize#define ins insert#define era erase#define RE return 0//ios::sync_with_stdio(false);//std::cin.tie(0);//<< setprecision(20)const int mod=(int)1000000007;const llint big=(llint)(2.19e16)+1;const long double pai=3.141592653589793238462643383279502884197;const long double ena=2.71828182845904523536;const long double eps=1e-7;template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}template <class T> void soun(T& ar){sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}llint lcm(llint a,llint b){return a/gcd(a,b) *b;}template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}using pli=pair<llint,int>;using daic=priority_queue<pli,vector<pli>,greater<pli>>;template <uint64_t MOD_ = 1000000007>class mint_base{public:static constexpr auto MOD = MOD_;static_assert(!(MOD <= 2), "MOD cannot be below 2.");static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしないstatic_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしないconstexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept{auto v = *this;return v += other;}constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept{auto v = *this;return v -= other;}constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept{auto v = *this;return v *= other;}constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept{a += other.a;if (MOD <= a) { a -= MOD; };return *this;}constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept{if (a >= other.a) {a -= other.a;}else {a = (a + MOD) - other.a;}return *this;}constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept{a *= other.a;a %= MOD;return *this;}constexpr mint_base<MOD> operator+()const noexcept { return *this; }constexpr mint_base<MOD> operator-()const noexcept{return{ MOD - a, mod_value_tag{} };}constexpr mint_base<MOD>& operator++() noexcept{if (MOD <= ++a) { a = 0; };return *this;}constexpr mint_base<MOD>& operator--() noexcept{if (a <= 0) { a = MOD; };--a;return *this;}constexpr mint_base<MOD> operator++(int) noexcept{auto tmp = *this;++*this;return tmp;}constexpr mint_base<MOD> operator--(int) noexcept{auto tmp = *this;--*this;return tmp;}constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept{a = other.a;return *this;}constexpr operator uint64_t()const noexcept{return a;}constexpr explicit operator unsigned()const noexcept{return (unsigned)a;}static constexpr uint64_t getmod() noexcept{return MOD;}constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {}constexpr mint_base()noexcept : a(0) {}struct mod_value_tag {};constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}private:uint64_t a;};//mint_base型のstreamへの出力template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i){os << (uint64_t)i;return os;}//mint_base型のstreamからの入力template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i){uint64_t tmp;is >> tmp;i = tmp;return is;}int main(void){static mint_base<> niko[10010][10010];niko[0][0]=1;mint_base<> n;llint k,i,j,h;cin>>n>>k;for(i=0;i<k+5;i++){for(j=0;j<=i;j++){niko[i+1][j]+=niko[i][j];niko[i+1][j+1]+=niko[i][j];}}//二項係数mint_base<>bel[10010];bel[0]=1;for(i=1;i<=k;i++){for(j=0;j<i;j++){bel[i]+=bel[j]*niko[i+1][j];}mint_base<> bgen=i+1,g=1;for(h=0;h<30;h++){if((mod-2)&(1<<h)){g*=bgen;}bgen*=bgen;}bel[i]*=(mod-g);}cerr<<bel[26]*mint_base<>(6)<<endl;mint_base<> rui[10010];rui[0]=1;n+=1;for(i=1;i<=10005;i++){rui[i]=rui[i-1]*n;}mint_base<> ans=0;for(i=0;i<=k;i++){ans+=niko[k+1][i]*bel[i]*rui[k+1-i];}mint_base<> bgen=k+1,g=1;for(h=0;h<30;h++){if((mod-2)&(1<<h)){g*=bgen;}bgen*=bgen;}cout<<ans*g<<endl;RE;}