백준 12911 / C++

https://www.acmicpc.net/problem/12911

12911번: 좋아하는 배열

 

[ 풀이 ] 

dp[i][j]를 길이 i이고 j로 끝나는 조건을 만족하는 개수라고 하자. 

전체 경우의 수는 dp[N][1]+...+dp[N][K]가 된다. 문제조건의 여사건은 A가 B의 배수라는 것이다. 

즉, 뒤로갈수록 앞의 약수가 되면 된다. WLOG 순서를 뒤집어서 뒤로 갈수록 앞의 배수가 되도록 해도 된다. 

dp[i+1][j]=dp[i][1]+....+dp[i][k]-sum(dp[i][u]) (u는 j의 배수) 임을 알 수 있다. 

S(i)=dp[i][1]+...+dp[i][k]라고 정의하면, dp[i+1][j]=S[i]-sum(dp[i][u])이다.

S[i]는 누적합으로 처리되고 sum(dp[i][u])를 구하는데는 K/i시간이 걸린다. 

따라서 O(N(K/1+K/2+...+K/K))=O(NKlogK)에 구해줄 수 있다. 좋은 문제.

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, K, sum[11], dp[11][100001];
const ll mod = 1e9 + 7;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K;
	for (int j = 1; j <= K; j++) dp[1][j] = 1; // base 
	sum[1] = K;
	// dp[x][y]=sum[x]-sigma(dp[x-1][z])
	for (int x = 2; x <= N; x++) {
		for (int y = 1; y <= K; y++) {
			dp[x][y] += sum[x - 1];
			ll temp = 0;
			for (int z = 2 * y; z <= K; z += y) {
				temp += dp[x - 1][z];
				temp %= mod;
			}
			dp[x][y] = sum[x - 1] - temp;
			if (dp[x][y] < 0) dp[x][y] += mod;
			// sum[x] 갱신 
			sum[x] += dp[x][y];
			sum[x] %= mod;
		}
	}
	cout << sum[N];
}