MIku

这是一道数学题，可以推式子（我推错了）

这是一道dp，完全没想到它是。

所以说我把我的错误式子缝缝补补，加上个dfs

过了。

大体思想就是利用插板法求出每个盒子可以装几个球的方案，

然后因为同一个盒子内部的球是无序的，所以说用一点点排列的知识加上dfs的框架处理一下，然后就过了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long Ariche(int x){
    int tem=1;
    for(int li=1;li<=x;++li){
        tem*=li;
    }
    return tem;
}
long long n,r;
long long simex;
void dfs(int la,int now,int cnt,int ans){
    if(cnt>r-1)
    return ;
    if(now==n){
    //  cout<<"342342";
        if(cnt==r-1){
            simex+=ans;
            return ;
        }
        else{
            return ;
        }
    }
    dfs(la,now+1,cnt,ans);
    dfs(now,now+1,cnt+1,ans*=(Ariche(n-la)/Ariche(n-la-(now-la))/Ariche(now-la)));
}
int main(){
    cin>>n>>r;
    //cout<<Ariche(n-1)/(Ariche(r-1)*Ariche(n-r+1))*Ariche(n);`  
    dfs(0,1,0,1);
    cout<<simex<<endl;                                                                                                                                                                  
    return 0;
}