题目

题目描述：
VMware实习生小V酷爱数学，有一天她在数学书上看到了这样一道题： $\sqrt{x} + \sqrt{y} = \sqrt{8}$ ，她很快解决了这个问题。
现在，她在思考，对于更一般的情况，存在多少本质不同的整数解：
$\sqrt{x_1} + \sqrt{x_2} + \sqrt{x_3} + ... + \sqrt{x_n} = \sqrt{m}$

答案对998244353取模。两组解本质不同当且仅当一组解无法通过交换变量的取值变成另一组。

输入描述：

两个整数n，m (n ≤ 1000，m ≤ 1000,000)

输出描述：
输出本质不同的解数，答案对998244353取模

解析

这道题思路非常简单，一下就想到了，但是实现把我捉弄了好一番。

思路讲解：

首先一点毋庸置疑：假如有个根号下的数已经化为最简（也就是系数*根号）的形式。只有在根号相同的时候才能进行相加。
既然根号下数相同时才能相加：也就是说，我们吧1 ~ n的每个数化简后的系数之和 = m化简后的系数。
所以这道题我们就知道意思了：就相当于我们给n个系数分配一个数m。通俗的说就是：给n个相同的桶子，分配m个相同的苹果，桶子可以为空，求分配方法数。
我记得！！高中学过！！我不会了，忘了！！！只记得是啥乘啥除啥再乘啥。
但是在和大佬们的许久讨论下，最后发现这个可以用dp写。

然后我们就知道了，这道题有两个重点：一个是把系数分解出来。第二个是dp求解情况数。

分解系数：

分解系数这一步很简单，就单纯的用素数筛就好啦，但是要注意的就是，同一个素数筛出来是奇数的话，只能选出最大的偶数次。
举个例子就是8分成3个2，所以只能取两个2。
```
ll mul = 1;
for (ll i = 2; i * i <= m; i++) {
    int cnt = 0;
    while (m % i == 0) {
        cnt++;
        m /= i;
    }
    for (int j = 0; j < (cnt >> 1); j++)
        mul = (mul * i) % MOD;
}
```
这样求完，mul自然就是m分解出来的系数了。

然后我们来讲dp。

动态规划最重要的就是递推和dp数组意义。

动态规划讲解：

首先我们很清楚我们的题目要干什么，就是给n个桶子分配m个苹果嘛。所以我们要找出dp数组含义和递推的过程。
那么我们清楚了解到变量有桶子和苹果，所以dp就是指n个桶子分m个苹果的情况。
然后讲到递推，我们我们对桶子和苹果的数量会进行质疑，就是桶子数（n）多于苹果数（m）的时候，明显就有桶子会是空着的，所以这些桶子不对答案产生影响：dp[n][m] = dp[m][m]。
那如果桶子数（n）少于苹果数（m）的时候呢？我们就会有两种情况，一个是所有桶子都是满的，另一个是有至少一个桶子是空的。
假如所有桶子都是满的，那么每个桶子一定都会有一个苹果打底对吧，这个苹果是不能动的！所有有和没有的情况数是一样的：dp[n][m] = dp[n][m-n]。
那如果有空桶子，空桶子就没有意义了对吧。空桶子至少有一个，那就去掉一个空桶子也是一样的对吧：dp[n][m] = dp[n-1][m]。

所以最后我们就可以得到这样的递推式：

if (j >= i)
        dp[i][j] = (dp[i][j - i] + dp[i - 1][j]) % MOD;
else
    dp[i][j] = dp[j][j];

所以根据递推，我们就有了两种方案：一个是递归，一个就是dp。

递归的话就是这样的：

ll f(ll n, ll m) {
    if (m == 1 || n == 0)   return 1;
    if (m > n)   return f(n, n) % MOD;
    return (f(n, m - 1) + f(n - m, m)) % MOD;
}

那如果dp的话就是：

for (int i = 1; i <= n; ++i) 
        for (int j = 0; j <= mul; ++j)
                if (j >= i)
            dp[i][j] = (dp[i][j - i] + dp[i - 1][j]) % MOD;
        else
            dp[i][j] = dp[j][j];

这道题压的挺死，递归会超时，所以我们还是dp求解啦

打代码嘿：

保存该保存的变量。
素数筛出我们的系数。
递推求解我们的答案。
详情看代码咯~

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);
//代码预处理区

const int MOD = 998244353;
const int MAX = 1e3 + 7;
int dp[MAX][MAX];
//全局变量区

//函数预定义区

int main() {
    IOS;
    ll n, m; cin >> n >> m;
    ll mul = 1;
    for (ll i = 2; i * i <= m; i++) {
        int cnt = 0;
        while (m % i == 0) {
            cnt++;
            m /= i;
        }
        for (int j = 0; j < (cnt >> 1); j++)
            mul = (mul * i) % MOD;
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) 
        for (int j = 0; j <= mul; ++j)
            if (j >= i)
                dp[i][j] = (dp[i][j - i] + dp[i - 1][j]) % MOD;
            else
                dp[i][j] = dp[j][j];
    cout << dp[n][mul] << endl;
    return 0;
}
//函数区

【牛客挑战赛40】A-小V和方程

题目

解析

AC代码

全站热榜