1935 - 拼车方案
时间限制 : 1 秒
内存限制 : 128 MB
现有n个人需要乘坐出租车，共有m辆车。1至4个人可以拼一辆车。问有多少种拼车方案。
题目输入
多组数据。一行一组，包括两个整数n，m。数据保证n，m均不超过300。
题目输出
每组数据输出一行，为答案（即方案数，请输出它模100007后的结果）。
输入/输出样例
输入格式
3 2 2 3
输出格式
6 0
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; }