HDU 5245 joyful（ 2015 Shanghai Metropolitan J ）

【题目链接】

http://acm.hdu.edu.cn/showproblem.php?pid=5245

【解题报告】

题目大意：给你一个N*M个格子的矩阵，每次任意挑两个格子（可以相同）染色，一共染色K次，求被染色的格子的个数的期望。

一道普通概率题，解题关键在于

如何求一个格子在k次染色后不被染色的期望。
           

现在我们来算第(i,j)个格子不被取中的概率

易知

S1=（i-1）^2*N^2;

S2=(N-j)^2*M^2;

其中S3=（i-1）^2*( N-j )^2被算了两次，所以需要被减去一次。

如果我们知道一个格子被染色的期望为P（i,j）

即第（i,j）个格子里有P(i,j)的部分被染色了。

那么累加所有格子的染色期望我们就能知道一个矩阵在K次染色后可能有多少个格子被染色。

另外，在计算过程中可能会爆int( 500^4 )，所以需要用long long来处理

【参考代码】

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

long long M,N,K;

long long C( int num )
{
    return (long long)num*(long long)num;
}

long long cal( long long i, long long j )
{
    long long ans=;
    ans+= C(N*(i-)) + C(N*(M-i)) + C(M*(j-)) + C(M*(N-j));
    ans-= C((i-)*(j-)) + C((i-)*(N-j)) + C((M-i)*(j-)) + C((M-i)*(N-j));
    return ans;
}

double pow_mod( double P, long long K )
{
    double ans=;
    while(K)
    {
        if(K&)ans*=P;
            P*=P;
        K/=;
    }
    return ans;
}

int main()
{
    int T,kase=;
    cin>>T;
    while(T--)
    {
        scanf("%I64d%I64d%I64d",&M,&N,&K);
        long long all=M*M*N*N;
        double ans=;
        for( long long i=; i<=M; i++ )
        for( long long j=; j<=N; j++ )
        {
            double P=cal(i,j)*/(all*);
            ans+=-pow_mod( P, K );
        }
        printf("Case #%d: %d\n", ++kase,(int)(ans+) );
    }
    return ;
}