結果
問題 |
No.1532 Different Products
|
ユーザー |
|
提出日時 | 2021-06-26 18:04:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 964 bytes |
コンパイル時間 | 2,034 ms |
コンパイル使用メモリ | 200,352 KB |
最終ジャッジ日時 | 2025-01-22 13:39:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 62 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:35:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 35 | scanf("%lld%lld",&n,&k); | ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=1e11; const int N=205,M=1e5+5; ll n,k,fac[N],two[N],ans; unordered_map<ll,ll>dp2; ll dp[N][M]; ll dfs(ll x,ll now){ if(!x)return 1; if(now>=M){ ll hash=x*INF+now; if(dp2.count(hash)){ return dp2[hash]; } if(now>=fac[x]){ return two[x]; } ll ans=0; ans=(ans+dfs(x-1,now)); ans=(ans+dfs(min(now/x,x-1),now/x)); return dp2[hash]=ans; } else{ if(~dp[x][now]){ return dp[x][now]; } ll ans=0; ans=(ans+dfs(x-1,now)); ans=(ans+dfs(min(now/x,x-1),now/x)); return dp[x][now]=ans; } } int main(){ scanf("%lld%lld",&n,&k); memset(dp,-1,sizeof dp); fac[0]=two[0]=1; for(int i=1;i<=40;++i){ two[i]=2ll*two[i-1]; } for(int i=1;i<=n;++i){ fac[i]=1ll*fac[i-1]*i; fac[i]=min(fac[i],INF); } for(int i=1;i<=min(n,k);++i){ ans+=dfs(i-1,k/i); } printf("%lld\n",ans); return 0; } /* 100 1000000000 1480348241 200 10000000000 44692356573 */