打气球(记忆化dp+数学期望)

过于菜QAQ

#include <cstdio>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
inline int R(){
    char t=getchar();int o=;bool F=;
    while(t<||t>)F|=t==,t=getchar();
    for(;t<&&t>;t=getchar())o=(o<<)+(o<<)+t-;
    return F?-o:o;
}
bool h[], s[];
int n;
double f[][];
int m;

double dp( int x, int y ){
    if( f[x][y] != - ) return f[x][y];
    if( ! x && ! y ) return f[x][y] = ;
    double ans = ;
    if( x ) ans += dp( x-, y ) * x * ( n - y );
    if( y ) ans += dp( x, y- ) * ( n - x ) * y;
    if( x && y ) ans += dp( x-, y- ) * x * y;
    return f[x][y] = (double) ( ans + (double) n * n ) / ( (double) n * ( x + y ) - x * y ) ;
}
int main()
{
//  freopen("data4.in","r",stdin);
//  freopen("shoot.out","w",stdout);
    n = R(); m = R(); int a, b;
    for( int i = ; i <= m; i ++ ){
        a = R(); b = R();
        h[a] = ; s[b] = ;
    }
    int c = , r = ;
    for( int i = ; i <= n; i ++ ){
        if( ! h[i] ) c ++;
        if( ! s[i] ) r ++;
    }

    for( int i = ; i <= n; i ++ )
        for( int j = ; j <= n; j ++ )
            f[i][j] = -;

    printf("%.2lf",dp(c,r));
    return ;
}