1935 - 拼车方案

3 2
2 3

6
0

Hint

	样例说明


	3个人拼2辆车，共有六种方案：


	方案一


	甲车：1


	乙车：23


	


方案二



甲车：2



乙车：13



<br />



<p>
	方案三
</p>
<p>
	甲车：3
</p>
<p>
	乙车：12
</p>
<p>
	<br />
</p>

方案四至六略，只需将甲乙颠倒即可。


<br />



本题有多种解法，数据范围不大，都能AC，欢迎踊跃尝试。

Solution C++

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll moder = 100007;
ll f[305][305][5];
int main(){
    int n, m;
    while(cin >> n >> m){
      memset(f, 0, sizeof(f));
      f[1][1][1] = f[2][1][2] = f[3][1][3] = f[4][1][4] = 1;
      for(ll i = 2; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
          for(int p = 1; p <= 4; ++p){
            if(i-p <= 0)
              continue;
            ll &s = f[i][j][p], *t = f[i-p][j-1], k = 1;
            if(p == 1) k = i;
            if(p == 2) k = i*(i-1)/2;
            if(p == 3) k = i*(i-1)*(i-2)/6;
            if(p == 4){
              //cout << "&&" << i << endl;
              k = i*(i-1)*(i-2)*(i-3)/24;
            }
            //if(k<0) cout << "!!!" << endl;
            s += (k*t[1])%moder;
            if(i-p > 1)
              s += (k*t[2])%moder;
            if(i-p > 2)
              s += (k*t[3])%moder;
            if(i-p > 3)
              s += (k*t[4])%moder;
            s = s%moder;
          }
        }
      ll ans = f[n][m][1]+f[n][m][2]+f[n][m][3]+f[n][m][4];
      ans = ans%moder;
      cout << ans << endl;
    }
    return 0;
}