VMware校园挑战赛-牛客挑战赛40 A 小V和方程

Description(凑字数)

VMware实习生小V酷爱数学，有一天她在数学书上看到了这样一道题： $\sqrt{x} + \sqrt{y} = \sqrt{8}$ ，她很快解决了这个问题。
现在，她在思考，对于更一般的情况，存在多少本质不同的整数解： $\sqrt{x_1} + \sqrt{x_2} + \sqrt{x_3} + ... + \sqrt{x_n} = \sqrt{m}$
答案对 $998244353$ 取模。两组解本质不同当且仅当一组解无法通过交换变量的取值变成另一组。

Solution

计数题, 考虑 $dp$ 做法, 首先 $m$ 能被拆成多个 $\sqrt{x_i}$ 相加, 那么举个例子
如: $\sqrt{32} = 4\sqrt2 = \sqrt2 + \sqrt2 + \sqrt2 + \sqrt2$ , 而 $\sqrt6$ 则拆不了, 只有一种方案
可以得出结论: $\sqrt{m}$ 要被拆成多个 $\sqrt{x_i}$ 相加, 必须能表示成 $x\sqrt{y}$
其中 $x$ 是 ${m}$ 的因子中能够被开方的最大因子 $k$ , 可以通过质因数分解求出
那么此时我们可以选择 $n$ 个数字，使得他们构成 $\sqrt{x_1} + \sqrt{x_2} + \sqrt{x_3} + ... + \sqrt{x_n} = \sqrt{m}$
其实也就等价于选择 $n$ 个数字的和能够等于 $k$
令 $dp[i][j]$ 表示当前和为 $i$ , 用了 $j$ 个数字的方案数，有状态转移方程

$dp[i][j] = dp[i][i] (i < j)$
$dp[i][j] = dp[i - j][i] + dp[i][j - 1] \ else$

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int mod = 998244353;
const int N = 1e5 + 5;
ll dp[5005][1005]; // i个球放到j个盒子里
int main() {
  int n, m;
  cin >> n >> m;
  ll cur = 1;
  for(ll i = 2; i <= m; i++) {
    if(m % i == 0) {
      while(m % (i * i) == 0) {
        cur *= i;
        m /= (i * i);
      }
    }
  } // cur 个球
  m = cur;
  for(int i = 0; i <= m; i++) {
    dp[i][1] = 1; // 一个盒子只有一种方案
  }
  for(int i = 1; i <= n; i++) {
    dp[0][i] = dp[1][i] = 1; // 1个球/ 0个球 只有一种方案
  }
  for(int i = 2; i <= m; i++) {
    for(int j = 2; j <= n; j++) {
      if(i < j) { // 球少于盒子
        dp[i][j] = dp[i][i];
      } else {
        dp[i][j] = dp[i - j][j] + dp[i][j - 1];
        dp[i][j] %= mod;
      }
    }
  }
  cout << dp[m][n];
  return 0; 
}