题意转换下就是 x1+x2+x3+...+xk=n,1<=xi<=m 。以样例为例子， x1+x2+x3+x4=7,1<=xi<=m ，设 y1=x1−1,y2=x2−1,y3=x3−1,y4=x4−1 ，则 y1+y2+y3+y4=7−4,0<=yi<=m−1 ，则问题转化为求 y1+y2+....+yk=sum 的非负整数解的问题。 方程整数解的问题在：http://www.cppblog.com/vici/archive/2011/09/05/155103.aspx 大概在博文中间的部分讲解了方程整数解问题 这里的答案就是 C(n-1,k-1)-C(k,1)C(n-1-m,k-1)+C(k,2)C(n-1-m*2,k-1)-…….一直累加到n-1-m*i小于k-1为止
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL CN[60][60]; int n,k,m; void init() { CN[0][0] = 1; for(int i = 1; i < 60; ++i) { CN[i][0] = 1; for(int j = 1; j <= i; ++j) CN[i][j] = CN[i-1][j] + CN[i-1][j-1]; } } LL C(int a, int b) { return CN[a][b]; } int main() { init(); ios::sync_with_stdio(false); while(cin >> n >> k >> m) { if(n<k||k>n*m) { cout << 0 << endl; continue; } LL res = C(n-1,k-1); for(int i = 1; n-1-i*m >= 0; ++i) { if(i&1) res -= C(k,i)*C(n-1-i*m,k-1); else res += C(k,i)*C(n-1-i*m,k-1); } cout << res << endl; } return 0; }