C++(g++ 7.5.0) 解法, 执行用时: 171ms, 内存消耗: 31828K, 提交时间: 2023-07-01 16:00:18

#include<bits/stdc++.h>

using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
ll dp[2010][2010];
int main(){
	ll ans = 0;
	int n,m;
	cin>>n>>m;
	dp[0][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int k=(i==1)?1:i*j/(i-1);
			if(i*j==k*(i-1)) k--;
			k = min(k,m);
			while(k>0&&i*j-k*(i-1)>=1&&i*j-k*(i-1)<=m){
				dp[i][j]+=dp[i-1][k];
				dp[i][j]%=mod;
				k--;
			}
		}
	}
	for(int i=1;i<=m;i++) ans=(ans+dp[n][i])%mod;
	cout<<ans<<endl;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 60ms, 内存消耗: 31812K, 提交时间: 2023-06-30 23:27:38

#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[2003][2003];
int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i=1ll;i<=m;++i)
	dp[1][i]=i;
	for(long long i=2ll;i<=n;++i)
	for(long long j=1ll;j<=m;++j)
	dp[i][j]=(dp[i][j-1ll]+dp[i-1][min(m,(i*j-1ll)/(i-1ll))]+1000000007ll-dp[i-1][max(0ll,(i*j-m-1ll)/(i-1ll))])%1000000007ll;
	printf("%lld",dp[n][m]);
	return 0;
}

pypy3 解法, 执行用时: 1621ms, 内存消耗: 29936K, 提交时间: 2023-06-30 19:55:10

import sys
input = lambda:sys.stdin.readline().strip()
M = lambda:map(int,input().split())
from collections import Counter
n,m = M()
mod = 10**9+7
a = Counter([0])
for i in range(n):
    b = Counter()
    x = i+1
    for v,vv in a.items():
        for j in range(x-v%x,m+1,x):
            b[v+j] += vv
            b[v + j] %= mod
    a = b
print(sum(a.values())%mod)