結果
問題 | No.1973 Divisor Sequence |
ユーザー |
![]() |
提出日時 | 2022-06-10 23:58:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 307 ms / 2,000 ms |
コード長 | 1,383 bytes |
コンパイル時間 | 4,065 ms |
コンパイル使用メモリ | 231,584 KB |
実行使用メモリ | 179,084 KB |
最終ジャッジ日時 | 2024-09-21 07:32:37 |
合計ジャッジ時間 | 7,027 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define INF 1000000000000000000 #define MOD 1000000007 #define MAX 500 int main(){ int N; ll M; cin>>N>>M; ll ans=1; for(ll p=2;p*p<=M;p++){ int cnt=0; while(M%p==0){ cnt++; M/=p; } if(cnt==0){ continue; } vector<vector<ll>> dp(N,vector<ll>(cnt+1,0)); for(int j=0;j<=cnt;j++){ dp[0][j]=1; } for(int i=0;i<N-1;i++){ for(int j=0;j<=cnt;j++){ dp[i+1][cnt-j]+=dp[i][j]; } for(int j=cnt;j>0;j--){ dp[i+1][j-1]+=dp[i+1][j]; } for(int j=0;j<=cnt;j++){ dp[i+1][j]%=MOD; } } ll sum=0; for(int j=0;j<=cnt;j++){ sum+=dp[N-1][j]; sum%=MOD; } ans*=sum; ans%=MOD; } if(M>1){ int cnt=1; vector<vector<ll>> dp(N,vector<ll>(cnt+1,0)); for(int j=0;j<=cnt;j++){ dp[0][j]=1; } for(int i=0;i<N-1;i++){ for(int j=0;j<=cnt;j++){ dp[i+1][cnt-j]+=dp[i][j]; } for(int j=cnt;j>0;j--){ dp[i+1][j-1]+=dp[i+1][j]; } for(int j=0;j<=cnt;j++){ dp[i+1][j]%=MOD; } } ll sum=0; for(int j=0;j<=cnt;j++){ sum+=dp[N-1][j]; sum%=MOD; } ans*=sum; ans%=MOD; } cout<<ans<<'\n'; }