結果
問題 | No.573 a^2[i] = a[i] |
ユーザー |
|
提出日時 | 2017-10-06 23:15:52 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 1,068 bytes |
コンパイル時間 | 1,164 ms |
コンパイル使用メモリ | 158,952 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-17 01:57:04 |
合計ジャッジ時間 | 2,322 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:57:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 57 | scanf("%d",&n); | ~~~~~^~~~~~~~~
ソースコード
#include <bits/stdc++.h> #define MOD 1000000007LL using namespace std; typedef long long ll; typedef pair<int,int> P; int n; ll fact[100001]; ll extgcd(ll a,ll b,ll& x,ll& y){ ll d=a; if(b!=0LL){ d=extgcd(b,a%b,y,x); y-=(a/b)*x; }else{ x=1; y=0; } return d; } ll mod_inverse(ll a,ll m){ ll x,y; extgcd(a,m,x,y); return (m+x%m)%m; } ll mod_fact(ll n,ll p,ll& e){ e=0; if(n==0)return 1; ll res=mod_fact(n/p,p,e); e+=n/p; if(n/p%2!=0){ return res*(p-fact[n%p])%p; } return res*fact[n%p]%p; } ll mod_comb(ll n,ll k,ll p){ if(n<0 || k<0 || n<k)return 0; ll e1,e2,e3; ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3); if(e1>e2+e3)return 0; return a1*mod_inverse(a2*a3%p,p)%p; } ll mod_pow(ll x,ll n){ ll res=1; while(n>0){ if(n&1)res=x*res%MOD; x=x*x%MOD; n>>=1; } return res; } int main(void){ scanf("%d",&n); ll ans=0; fact[0]=1; for(int i=1;i<=n;i++){ fact[i]=(ll)fact[i-1]*i%MOD; } for(int i=0;i<=n;i++){ ans+=mod_comb(n,i,MOD)*mod_pow(n-i,i)%MOD; ans%=MOD; } printf("%lld\n",ans); return 0; }