GGGCCCDDD

https://algospot.com/judge/problem/read/GGGCCCDDD

algospot.com :: GGGCCCDDD

더럽게 풀었음.

long long 값을 넘는 해결방법임.

중간 DP배열에 % (long long)1000000007을 하는게 키임.

또한 전체시간을 줄이는게 관건임.

다른 분은 행렬 규칙으로 해결한다고 함.

#include 
#include 

int DP[1001][1001];
long long DP2[2][1001];
long long DP3[1001][1001];
int S, N, M;
long long R;

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}
int get(int i, int j)
{
	int v = DP[i][j];
	if (v == 0)
		return DP[j][i];
	else
		return v;
}
void makeDP3()
{
	memset(DP3, 0, sizeof(DP3));

	for (int i = 1; i <= N; i++)
	for (int j = 1; j <= N; j++)
		++DP3[i][get(i, j)];
}
void update()
{
	int S2 = (S == 1) ? 0 : 1;

	for (int n = 1; n <= N; n++)
		if (DP2[S][n] > 0){
			for (int i = 1; i <= N; i++){
				if (DP3[n][i] > 0)
					DP2[S2][i] += (DP3[n][i] * DP2[S][n]) % (long long)1000000007;
			}
			DP2[S][n] = 0;
		}
	S = S2;
}

int main()
{
	memset(DP,0,sizeof(DP));

	for (int i = 1; i < 1001;i++)
	for (int j = i; j < 1001; j++)
		DP[i][j] = gcd(i, j);

	int T;
	for (scanf("%d", &T); T > 0; T--)
	{
		memset(DP2, 0, sizeof(DP2));
		R = 0;
		S = 0;
		scanf("%d %d", &N, &M);
		
		makeDP3();
		
		for (int n = 1; n <= N; n++)
		for (int i = 1; i <= N; i++)
			DP2[S][i] += DP3[n][i];
		
		for (int i = 2; i < M; i++)
			update();

		for (int i = 1; i <= N; i++)
			R += (i * DP2[S][i]) % (long long)1000000007;

		printf("%lld\n", R % (long long)1000000007);
	}
	return 0;
}