結果
問題 | No.1039 Project Euler でやれ |
ユーザー |
|
提出日時 | 2020-02-28 18:23:26 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 157 ms / 2,000 ms |
コード長 | 1,862 bytes |
コンパイル時間 | 2,276 ms |
コンパイル使用メモリ | 77,524 KB |
実行使用メモリ | 41,316 KB |
最終ジャッジ日時 | 2024-11-08 02:57:15 |
合計ジャッジ時間 | 5,943 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import java.util.Arrays;import java.util.Scanner;class Main {public static void main(String[] args) throws Exception {Scanner sc=new Scanner(System.in);int M=sc.nextInt();new Main().run(M);}final long MOD=(long)1e9+7;long pow(long a,long n) {n=(n%(MOD-1)+(MOD-1))%(MOD-1);long ret=1;for(;n>0;n>>=1,a=a*a%MOD)if(n%2==1)ret=ret*a%MOD;return ret;}long inv(long a) {return pow(a,MOD-2);}// (Z/2^1Z)^4 20160個// (Z/2^1Z)^2 \times (Z/2^2Z) 192個// (Z/2^1Z)^1 \times (Z/2^3Z) 16個// (Z/2^2Z)^2 96個// (Z/2^4Z)^1 8個// \prod (Z/p^k[i]Z)^u[i]// dp[i1][i2][i3]= \sum u[i]k[i], p^(i2), \sum u[i]long solve(long p,int e) {long[][][] dp=new long[e+1][e+2][e+1];dp[0][e+1][0]=1;for(int sumKU=0;sumKU<e;++sumKU) {for(int k=e+1;k>=1;--k) {for(int sumU=0;sumU<e;++sumU) {if(dp[sumKU][k][sumU]==0)continue;for(int nk=k-1;nk>=1;--nk) {for(int nu=1;sumKU+nk*nu<=e;++nu) {//(Z/p^nk)^nulong add=pow(p,nk*nu*sumU);for(int m=0;m<nu;++m) {add*=(pow(p,nk*nu)-pow(p,nu*(nk-1)+m))%MOD*pow(p,nk*sumU)%MOD;add%=MOD;}dp[sumKU+nk*nu][nk][sumU+nu]+=inv(add)*dp[sumKU][k][sumU]%MOD;dp[sumKU+nk*nu][nk][sumU+nu]%=MOD;}}}}}long ret=0;for(int i=1;i<=e;++i)for(int j=1;j<=e;++j)ret=(ret+dp[e][i][j])%MOD;ret=(ret%MOD+MOD)%MOD;return ret;}void run(int M) {long fac=1;for(long i=1;i<=M;++i)fac=fac*i%MOD;long ans=1;for(long div=2;div<=M;++div) {int e=0;while(M%div==0) {M/=div;++e;}if(e>0) ans=ans*solve(div,e)%MOD;}ans=ans*fac%MOD;System.out.println(ans);}static void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}}