小V和方程_牛客博客

分析

考虑对 $m$ 质因数分解，并将 $\sqrt{m}$ 提取成 $a\sqrt{b}$ 的最简形式。
如果要满足 $\sqrt{x_1}+\sqrt{x_2}+...+\sqrt{x_n}=a\sqrt{b}$ ，对于任意一个 $\sqrt{x}$ 而言，化简后都带有 $\sqrt{b}$ 。

于是问题被转化成 $a$ 能被表示为多少种 $n$ 个数的和，其中可以有 $0$ 。

也即 $a$ 个苹果放在 $n$ 个篮子里有多少种放法。

此处可用dp解， $dp[i][j]$ 表示 $j$ 个苹果放在 $i$ 个篮子里方法总数。

转移方程为 $dp[i][j] = dp[i][j - i] + dp[i - 1][j]$

应牛友要求详细解释一下：

把5个苹果放进2个篮子里，我们已经知道了五个苹果放进一个篮子里有多少种方法，那么现在多出来了一个篮子，考虑篮子不空的情况，先把所有的篮子都放一个苹果，然后再加上3个苹果放进两个篮子里的方案数量。

也就是说对于 $dp[i][j] = dp[i][j - i] + dp[i - 1][j]$ ， $dp[i - 1][j]$ 是空了篮子的方案， $dp[i][j - i]$ 是一个篮子都不空的方案。无论空多少个篮子呢，都包含在 $dp[i-1][j]$ 里面：这里是类似递归的理解，空一个篮子里包含了空一个篮子里的空一个篮子。

solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 998244353;
const int maxn = 1005;
ll dp[maxn][maxn];
ll f(ll n, ll m){  // m个苹果 n个篮子
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            if (j >= i)  dp[i][j] = (dp[i][j - i] + dp[i - 1][j]) % mod;
            else dp[i][j] = dp[j][j];
    return dp[n][m];
}
int main() {
    int n, m;
    cin >> n >> m;
    ll a = 1;
    for(ll i=2;i*i<=m;++i)
        while(m%(i*i)==0)a*=i,m/=(i*i);
    cout << f(n,a) << endl;
    return 0;
}