結果

問題 No.1532 Different Products
ユーザー V_Melville
提出日時 2021-06-26 18:17:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 742 ms / 4,000 ms
コード長 1,017 bytes
コンパイル時間 2,151 ms
コンパイル使用メモリ 199,696 KB
最終ジャッジ日時 2025-01-22 13:40:42
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 62
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:37:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |         scanf("%lld%lld",&n,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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(now>=M){
		ll hash=x*INF+now;
		if(dp2.count(hash)){
			return dp2[hash];
		}
		if(now>=fac[x]){
			return dp2[hash]=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];
		}	
		if(now>=fac[x]){
			return dp[x][now]=two[x];
		}
		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(ll i=1;i<=min(n,k);++i){
		ans+=dfs(min(k/i,i-1),k/i);
	}
	printf("%lld\n",ans);
	return 0; 
}
/*
100 1000000000
1480348241
200 10000000000
44692356573
*/
0