A 小V和方程（划分 数dp）

A:https://ac.nowcoder.com/acm/contest/5555/A

分析：n个根号数的和等于m，求本质不同的方案数，对于m一顶满足m=a*√x，那么实际上就是a个球放入n个箱子中的整数划分问题，（箱子可为空）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int M=1e3+3;
const int mod=998244353;
int dp[M][M];///i个球放在j个篮子中的方案数
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int now=1;
    for(int i=2;i<=m;i++){
        if(m%i==0){
            while(m%(i*i)==0){
                m/=(i*i);
                now*=i;
            }
        }
    }
    ///now个数放在n个篮子中
    dp[0][0]=1;
    for(int i=0;i<=now;i++)
        for(int j=1;j<=n;j++){
            if(i<j)
                dp[i][j]=dp[i][i];
            else///      空了篮子的方案+一个篮子都不空的方案  
                dp[i][j]=dp[i][j-1]+dp[i-j][j];
            dp[i][j]%=mod;
        }
    printf("%d
",dp[now][n]);
    return 0;
}