結果

問題 No.665 Bernoulli Bernoulli
ユーザー snrnsidy
提出日時 2021-10-22 20:21:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 883 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 42,108 KB
最終ジャッジ日時 2025-01-25 03:01:26
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 2 MLE * 1
other WA * 14 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:34:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%d %d",&n,&k);
      |         ~~~~~^~~~~~~~~~~~~~~

ソースコード

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