結果
問題 |
No.573 a^2[i] = a[i]
|
ユーザー |
![]() |
提出日時 | 2021-01-04 23:50:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,028 bytes |
コンパイル時間 | 1,675 ms |
コンパイル使用メモリ | 191,444 KB |
最終ジャッジ日時 | 2025-01-17 09:42:32 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/all> using namespace std; //using namespace atcoder; typedef long long ll; typedef pair<ll,ll> P; //typedef modint998244353 mint; #define rep(i,a,b) for(ll i=a;i<b;i++) #define rrep(i,a,b) for(ll i=a;i>=b;i--) ll modpow(ll a,ll n,ll MOD){ ll res=1; while(n>0){ if(n&1) res=res*a%MOD; a=a*a%MOD; n>>=1; } return res; } const ll MAX=200005; const ll MOD=1000000007; ll fac[MAX],finv[MAX],inv[MAX]; void COMinit(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(ll i=2;i<MAX;i++){ fac[i]=fac[i-1]*i%MOD; inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD; finv[i]=finv[i-1]*inv[i]%MOD; } } ll COM(ll i,ll j){ if(i<j) return 0; if(i<0||j<0) return 0; return fac[i]*(finv[j]*finv[i-j]%MOD)%MOD; } ll n; ll ans; int main(void){ cin.tie(0); ios::sync_with_stdio(0); cin>>n; COMinit(); for(int i=1;i<=n;i++){ ans=(ans+COM(n,i)*modpow(i,n-i,MOD))%MOD; } cout<<ans<<endl; }