12911 : 좋아하는 배열

풀이

dp[i][j] = 길이가 i이고, 첫번째 숫자가 j

나머지 연산에 주의하자.

코드

#include <stdio.h>

typedef long long ll;

const int mod = 1000000007;

int N, K;
int dp[11][100001];
ll sum[11];

int main() {
	scanf("%d %d", &N, &K);

	for (int i = 0; i <= K; ++i) dp[1][i] = 1;
	sum[1] = K;
	for (int i = 2; i <= N; ++i) {
		sum[i - 1] += mod;
		for (int j = 1; j <= K; ++j) {
			ll temp = 0;
			for (int k = j + j; k <= K; k += j) {
				temp += dp[i - 1][k];
				temp %= mod;
			}
			dp[i][j] = sum[i - 1] - temp;
			dp[i][j] %= mod;
			sum[i] += dp[i][j];
			sum[i] %= mod;
		}
	}
	printf("%lld", sum[N]);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-08 12:09

Read more posts by this author