結果
問題 | No.573 a^2[i] = a[i] |
ユーザー |
![]() |
提出日時 | 2017-10-07 11:32:30 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 904 bytes |
コンパイル時間 | 623 ms |
コンパイル使用メモリ | 99,596 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 21:59:52 |
合計ジャッジ時間 | 2,245 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
class C{ // public: long[] fac, inv; long mod=1_000_000_000+7; this(int n){ fac.length=n+1; fac[0]=fac[1]=1; for(int i=2; i<=n; i++) fac[i]=i*fac[i-1]%mod; inv.length=n+1; for(int i=0; i<=n; i++) inv[i]=pow(fac[i], mod-2); } long pow(long a, long x){ if(x==0) return 1; else if(x==1) return a; else if(x%2==0) return pow(a*a%mod, x/2); else return a*pow(a, x-1)%mod; } long comb(int n, int k){ if(n<k) return 0; else return (fac[n]*inv[n-k]%mod)*inv[k]%mod; } } void main(){ import std.stdio, std.string, std.conv, std.algorithm; int n; rd(n); auto c=new C(n); long cnt=0, mod=c.mod; for(int i=1; i<=n; i++){ (cnt+=c.comb(n, i)*c.pow(i, n-i)%mod)%=mod; } writeln(cnt); } void rd(T...)(ref T x){ import std.stdio, std.string, std.conv; auto l=readln.split; foreach(i, ref e; x){ e=l[i].to!(typeof(e)); } }