[UVA][排列組合] 10634 - Say NO to Memorization
Problem C
Say NO to
Memorization
Input: Standard Input
Output: Standard Output
Time Limit: 2 Seconds
Kamran has a very simple but uncommon (I mean cannot just be copied from pages of your book) problem for you. Can you prove by solving it that you are not one of those who only memorize pseudo codes before algorithm exam? The problem is stated below:
A general equation of second degree with two variables is ax2 + by2 + cxy + dx + ey + f = 0, You can see that it has six terms on the left hand side (LHS). A general equation of second degree with two variables and with only terms of even degree is ax2 + by2 + cxy + d = 0, which has only four terms in LHS. A general equation of third degree with two variables with only terms of odd degree is ax3 + by3 + cx2y + dxy2 + ex + fy = 0, which has only six terms in LHS. Given the degree (n) and number of variables (v) your job is
a) If n is even you should determine the number of terms in a general equation of n-degree with v variables and only with terms of even degree OR
b) If n is odd you should determine the number of terms in a general equation of n-degree with v variables and only with terms of odd degree.
Input
Output
For each line of input produce one line of output. This line contains one integer T that indicates the number of terms on the left hand side of a general equation of degree n, v variables and only of odd degree terms when n is odd or only of even degree terms when n is even. You can assume that the input will be such that output will always fit in a 64-bit signed integer.
Sample Input Output for Sample Input
|
2 2 4 2 20 10 0 0 |
4 9 17978389
|
Problemsetter: Shahriar Manzoor, Member of Elite Problemsetters' PanelSpecial Thanks to Derek Kisman, Member of Elite Problemsetters' Panel (Alternate Sol)
“No matter how loud I shout nothing will change as the people relatedto the system don’t want to change it. The big oil producingcompanies never want solar cars in the market, do they?” 排列組合，x1 + x2 + x3 ... + xn = v // v <= V, 且 v%2 = V%2
計算所有可能方法總數。
利用 OOOO||| 的排列方式去計算方法數。
#include <stdio.h>
#include <string.h>
using namespace std;
long long C[2005][2005] = {};
long long R[2005][2005] = {};
void init() {
C[0][0] = 1;
for(int i = 1; i < 2005; i++) {
C[i][0] = 1;
for(int j = 1; j <= i; j++)
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
for(int v = 1; v <= 1000; v++) {
for(int n = 0; n <= 1000; n++)
R[n][v] = C[n+v-1][v-1] + (n >= 2 ? R[n-2][v] : 0);
}
}
int main() {
init();
int n, v;
while(scanf("%d %d", &n, &v) == 2) {
if(n == 0 && v == 0)
return 0;
printf("%lld\n", R[n][v]);
}
return 0;
}