結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー snrnsidy
提出日時 2021-10-22 20:21:55
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
(最新)
MLE  
(最初)
実行時間 -
コード長 883 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 391 ms
コンパイル使用メモリ 58,200 KB
実行使用メモリ 433,536 KB
最終ジャッジ日時 2026-06-23 10:26:13
合計ジャッジ時間 7,389 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1 -- * 1
other -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<cstdio>
#include<algorithm>
#define mod 1000000007LL

using namespace std;
using ll=long long;

ll c[10001][10001];
ll ans[10001];

pair<ll,ll> solve(ll a,ll b){
	if(!b)return {1,0};
	pair<ll,ll> ret=solve(b,a%b);
	ll x=ret.second,y=ret.first-(a/b)*ret.second;
	ll t=x/b;
	x+=b*t;y-=a*t;
	if(x<0){x+=b;y-=a;}
	return {x,y};
}

int main(){
	int n,k;
	ll exp,tmp,div;
	for(int i=0;i<=10000;++i){
		for(int j=0;j<=10000;++j){
			if(i<j)break;
			if(!j)c[i][j]=1;
			else{
				c[i][j]=c[i-1][j]+c[i-1][j-1];
				c[i][j]%=mod;
			}
		}
	}
	scanf("%d %d",&n,&k);
	ans[0]=n;
	exp=n+1;
	for(int i=1;i<=k;++i){
		exp*=n+1;
		exp%=mod;
		tmp=exp+mod-1;
		tmp%=mod;
		for(int j=2;j<=i+1;++j){
			tmp-=c[i+1][j]*ans[i-j+1];
			tmp%=mod;
			if(tmp<0)tmp+=mod;
		}
		div=solve(c[i+1][1],mod).first;
		ans[i]=tmp*div;
		ans[i]%=mod;
		if(ans[i]<0)ans[i]+=mod;
	}
	printf("%lld",ans[k]);
}
0