今天真的被虐死了。。

国科大的这种神牛啊！！！   做了5个小时的题目，只做出了一个题目。还是在殷牛的提示下才做出来的呢。

题目大一如下：We choose an integer K (K > 0). Then we generate N (N > 0) integers one by one randomly, each of them is in range [0, K - 1], and the possibility of that its value equals to any integer in this range is 1/K.
Can you tell us the exception of the number of distinct integers in that N integers?
初始一看，我就认为这是一个排列组合的问题呢。结果就和飞神讨论了起来，果不其然，我把飞神给黑了。这个题目居然是用DP来做哦。就像斌牛所说的那样，不要把自己的想法强加给队友，这样会让队友按着你的思维来想，不利于发挥队伍的思维优势。

题目要求的是：取数后，不同数字的“个数”的期望值

很容易让人以为这就是个求排列组合的问题，但是看了数据后就被震精了，1<=N,K<=1000，排个毛线啊 ，果断超了int 啊 ！

后来经过殷牛的提示我才发现，这应该用DP来做，根据前面的状态来推算后面的状态。

解题的关键在那里呢 ？ 嘿嘿，关键在于状态的表示问题上面。在做题开始的时候，我一直直接用f[K][N]来表示推算到K的单位长度后，取N个数中不同数字的个数的期望值，为什么我错了呢？ 原因有以下几点：（1）推长度的关系式不好写，整个应该确定一个总数再退 （2）如果状态表示的是期望值，那么递推之间的关系就难以得出，前后等于是没有联系

因此，表示状态较为合适的方法应该是：用f[i][j] 表示：推算到第i个数的时候，其中有j个数相同的概率值，即不考虑总的总长度，将其当做恒量。

这样的话其状态转移方程就很容易得出来了：

 f[i][j]=f[i-1][j]*j/K+f[i-1][j-1]*(K-j+1)/K;

（注：取得数与前面取过的数相同的概率为j/K，如果不同，那么前面就取过了(j-1)个数，因此，不同的概率为((K-j+1)/K)）

同时还要考虑边界条件，不过根据状态的含义，不难得出边界的值为： f[i][1]=(1/K)^(i-1); f[1][i]=0（第二项中i>1)

于是直接DP，最后ans=求和 f[n][i]*i；

具体的代码如下：

＃i nclude <iostream>
＃i nclude <cstdio>
using namespace std;

double f[1010][1010],ans;

int main()
{
    int maxn,minn,N,K,t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&K,&N);
        minn=min(N,K);  maxn=max(K,N);
        f[1][1]=1;
        for (int i=2; i<=maxn; i++) f[i][1]=f[i-1][1]/K,f[1][i]=0;
        for (int i=2; i<=maxn; i++)
        {
            for (int j=2; j<=maxn; j++)
                if (i<j) { f[i][j]=0; continue; }
                else f[i][j]=(f[i-1][j]*j+f[i-1][j-1]*(K-j+1))/K;
        }
        ans=0;
        for (int i=1; i<=minn; i++)
            ans+=f[N][i]*i;
        printf("%.5lf\n",ans);
    }
    return 0;
}

感觉maxn和minn用得也不是很好，但是DP的时候，由于后面的值不会影响前面的值，所以稍稍扩大了一点范围，以求保险。。。