SRM545 Div2 Hard(1000) SpacetskE

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;
}};