SRM545 Div2 Hard(1000) SpacetskE
(x,0)を出発して、最後に(tx,ty)で信号を発するとすると、途中で通る格子点は出発点を含めて、gcd(tx-x,ty)個。その中から、K-1点を選ぶ。これを、出発点と最後に信号を発する点の各組合わせに対して、足し合わせる。
#include <algorithm> using namespace std; long long C[256][256]; 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 SpacetskE{public: int countsets( int L, int H, int K ) { const int M = 1000000007; if ( K==1 ) return (L+1)*(H+1)%M; for ( int i=0; i<256; 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; for ( int x=0; x<=L; x++ ) for ( int tx=0; tx<=L; tx++ ) for ( int ty=1; ty<=H; ty++ ) { long long d = gcd(abs(tx-x),ty); ans += C[d][K-1]; ans %= M; } return (int)ans; }};