TIOJ 1291 . G.N 箱M 球

題目鏈接:https://tioj.ck.tp.edu.tw/problems/1291

可知放m球的可能性可從m-1球推得

用DP求解

得轉移曲線為

dp[i][j]=dp[i][j-1]*i+dp[i-1][j-1]

放i箱j-1球加一球可以放在箱子的任何位置,也就是i種可能性

但也有可能前j-1球只放在前i-1箱中,則第j球獨立放在一箱

以下為code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define AC ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

int main()

{

AC

ll n,m,dp[201][201];

memset(dp,0,sizeof(dp));

dp[0][0]=1;

for(ll i=1;i<201;i++)

for(ll j=1;j<201;j++)

dp[i][j]=(dp[i][j-1]*i+dp[i-1][j-1])%1000000;

while(cin>>n>>m&&n&&m)

{

ll r=0;

for(ll i=1;i<=n;i++)

r=(r+dp[i][m])%1000000;

cout<<r<<'\n';

}

}

要特別注意的是寫dp題目時要設定好初始值,否則會引發特殊情況導致WA,我在這裡卡超久...
還有就是%的運算優先級順序也要特別注意