SRM545 Div1 Medium(500) 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; }};