반응형
https://algospot.com/judge/problem/read/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;
}
반응형