题目链接
数据范围: n,m <= 1e3 , 答案对 1e9 + 7 取模
假设前\(i\)个数的和为\(r * i\) , 前\(i - 1\)个数的和为\(k * (i - 1)\) , 第\(i\)个数为\(t\) , 那么则有
由于\(1 <= t <= m\) ， 所以
\[1 <= r * i - k * (i - 1) <= m \]设状态\(dp[i][j]\)表示前\(i\)个数字的和是\(i * j\)的方案数。其中\(j\)对应的就是上面式子中的\(r\) , 将所有满足要求的\(k\)对应的贡献累加起来即可。
\[\lceil{\frac{r * i - m}{i - 1}}\rceil <= k <= \lfloor{\frac{r * i - 1}{i - 1}}\rfloor \]#include<iostream>
using namespace std;
const int N = 2e3+10 , mod = 1e9+7;
int n , m;
int dp[N][N] , Sum[N];
int main()
{
int Answer = 0;
cin >> n >> m;
for(int i = 1 ; i <= m ; ++i)
dp[1][i] = 1;
for(int i = 2 ; i <= n ; ++i)
{
for(int j = 1 ; j <= m ; ++j) Sum[j] = (Sum[j-1] + dp[i-1][j]) % mod;
for(int j = 1 ; j <= m ; ++j)
{
int l = max((j * i - m + i - 2) / (i - 1) , 1);
int r = min((j * i - 1) / (i - 1) , m);
dp[i][j] = (Sum[r] - Sum[l - 1] + mod) % mod;
}
}
for(int i = 1 ; i <= m ; ++i)
Answer = (Answer + dp[n][i]) % mod;
cout << Answer << endl;
return 0;
}