結果

問題 No.665 Bernoulli Bernoulli
ユーザー snrnsidysnrnsidy
提出日時 2021-10-22 20:21:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 883 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 46,204 KB
実行使用メモリ 784,092 KB
最終ジャッジ日時 2023-10-24 09:55:23
合計ジャッジ時間 11,203 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 MLE -
testcase_17 MLE -
testcase_18 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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