Problem F: ZL's Prob.1

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 33 Solved: 10
[Submit][Status][Web Board]

Description

It is said that the Martian are going to have a competition with us.
They give us N kinds of different characters(not just letters), and a number K, we have an expression f which is equal as (c1+c2+c3+……+cn)^k. [ci is one of the giving characters].
Now, what they want to know is number of different terms after f is expanded; do help the earth.

Input

There are muliply test cases;
for each test case,
there is only a line contains the two natural numbers N and K separated by blanks. As you can observe, N and K are both at least 1.

Output

For each test case there is a line contains an answer.
You may safely assume that each answer fits into a 64-bit unsigned integer.

Sample Input

3 4

Sample Output

HINT

f = (c1+c2+c3)^4 = c1^4 + c2^4 + c3^4 + 4*c1^3*c2 + 4*c1^3*c3 + 4*c2^3*c3 + 4*c2^3*c1 + 4*c3^3*c1 + 4*c3^3*c2 + 6*c1^2*c2^2 + 6*c2^2*c3^2 + 6*c3^2*c1^2 + 4*c1*c2*c3^2 + 4*c1*c2^2*c3 + 4*c1^2*c2*c3

so the total number of the expansion is 15.

分析:

1.设结果为F(N,K);

2.对于N个变量和的K次方，可以分解为N-1个变量为整体与1个变量和的K次方,则F(N,K)=F(N-1,0)+F(N-1,1)+F(N-1,2)+...+F(N-1,K-1)+F(N-1,K);同理可以这样表示F(N+1,K);综合一下，F(N+1,K)=F(N,K)+F(N+1,K-1);

　F(N,0)=1;F(N,1)=1;F(0,K)=1;F(1,K)=1;

3.因为输出可以用long long表示，故可以推测N,K都在1000内；

4.递归求解F(N,K)并将每个求过的值保存于f[n][k],已经求过的就直接返回结果;

#include <cstdio>
#include <iostream>
using namespace std;

long long f[1000][1000];

long long F(long long N,long long K)
{
    if (f[N][K]!=0)return f[N][K];
    if (K==1)return N;
    if (N<=1||K==0)return 1;
    return f[N][K]=F(N-1,K)+F(N,K-1);
}
long long fact(long long N)
{
    if (N<=1)return 1;
    else return N*fact(N-1);
}

int main(void)
{
    ios::sync_with_stdio(false);
    long long N,K;
   while(cin>>N>>K)
  cout<<F(N,K)<<endl;
//    for (N=2;N<10;N++)
//    {
//        for (K=1;K<9;K++)
//        cout<<(double)(F(N,K))*fact(K)/(fact(K+N-1)*fact(N))<<endl;
//        cout<<"--------"<<endl;
//    }
    return 0;
}

View Code