SRM545 Div1 Medium(500) Spacetsk

Spacetsk

K=1ならば、格子点の個数なので、(L+1)(H+1)。垂直に発射する場合は、C(a,b)をa個の中からb個取る場合の数として、(L+1)C(H+1,K)。斜めに発射する場合、発射地点から(+dx,+dy)の格子点で最後に信号を発するとすると、途中に通過する格子点の個数は発射地点を含めて、gcd(dx,dy)個。その中から、K-1個を選ぶ。発射地点の選び方は(L-dx+1)通り。

long long C[2048][2048];

long long gcd(long long a,long long b)
    {long long t;if(a>b)t=a,a=b,b=t;while(a)t=a,a=b%a,b=t;return b;}

class Spacetsk{public:
int countsets( int L, int H, int K )
{
    const int M = 1000000007;

    if ( K==1 )
        return (int)((L+1)*(H+1)%M);

    for ( int i=0; i<2048; i++ )
    {
        C[i][0] = C[i][i] = 1;
        for ( int j=1; j<i; j++ )
            C[i][j] = (C[i-1][j-1]+C[i-1][j])%M;
    }

    long long ans = 0;

    ans += (L+1)*C[H+1][K];
    ans %= M;

    for ( int dx=1; dx<=L; dx++ )
    for ( int dy=1; dy<=H; dy++ )
    {
        long long d = gcd(dx,dy);
        ans += C[d][K-1]*2*(L-dx+1);
        ans %= M;
    }

    return (int)ans;
}};