結果
問題 | No.797 Noelちゃんとピラミッド |
ユーザー |
![]() |
提出日時 | 2019-03-15 21:49:21 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 1,051 bytes |
コンパイル時間 | 560 ms |
コンパイル使用メモリ | 72,248 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 20:48:30 |
合計ジャッジ時間 | 4,813 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<queue> #include<deque> using namespace std; typedef long long int LL; typedef pair<int,int> P; typedef pair<int,pair<int,int> > PP; typedef pair<LL,int> LP; LL nCk[100005]; const LL MAX=1e9+7; long long int pow_mod(long long int p_a,long long int p_n,long long int p_p=1e9+7){ //p_a^p_n mod p_p long long int p_b=1,p_t=1; for(;p_b<=p_n;p_b<<=1); for(p_b>>=1;p_b>0;p_b>>=1){ p_t*=p_t; if(p_t>=p_p)p_t%=p_p; if(p_n&p_b)p_t*=p_a; if(p_t>=p_p)p_t%=p_p; } return p_t; } void nCk_mod(int c_n,long long int c_mod=1e9+7){ long long int c_a=1; nCk[0]=1,nCk[c_n]=1; for(int i=0;i<c_n/2;i++){ c_a*=(c_n-i); if(c_a>=c_mod)c_a%=c_mod; c_a*=pow_mod(i+1,c_mod-2,c_mod); if(c_a>=c_mod)c_a%=c_mod; nCk[i+1]=c_a,nCk[c_n-i-1]=c_a; } } int main(){ int n; LL a,s=0; cin>>n; nCk_mod(n-1); for(int i=0;i<n;i++){ cin>>a; s+=a*nCk[i]; if(s>=MAX)s%=MAX; } cout<<s<<endl; return 0; }