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