SRM 513 D1 500 PerfectMemory

#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <float.h>
using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)

class PerfectMemory {
    public:
    double getExpectation(int N, int M)
    {
        int n=N*M;
        vector<vector<double> > dp(n+1,vector<double> (n+1));//unknown card, known
        REP(i,n+1)
        FOR(j,i,n+1)
            dp[i][j]=(i+j)/2;
        REP(i,n+1)
        REP(j,i)
        if(((i+j)%2)==0)
        {
            double u=i,k=j;
            dp[i][j]+=(1+dp[i-2][j+2])*((u-k)/u*(u-k-2)/(u-1));
            dp[i][j]+=(1+dp[i-2][j])*((u-k)/(u*(u-1)));
            dp[i][j]+=(2+dp[i-2][j])*((u-k)/u*(k)/(u-1));
            if(j)
                dp[i][j]+=(1+dp[i-1][j-1])*(k/u);
        }
        return dp[n][0];
    }
};