[12937] 좋아하는 배열 2

개인적으로는 자력으로 푼 dp 문제중에서는 가장 어려웠지 않나... 싶습니다.
태그에는 berlekamp-massey 알고리즘이 있지만 여기서는 이걸 사용하지 않고 해설하겠습니다.
 
풀이 전반적으로 선형대수학이 많이 사용됩니다. 기본적인 행렬연산 정도를 사전지식으로 요구합니다.
 

풀이

문제의 3번째 조건

배열에서 연속한 수가 $A$와 $B$일 때, $A \leq B$ 또는 $A % B \neq 0$ 을 만족해야 한다.

 
는 다르게 말하면 $A$는 $B$ 이하거나 2 이상의 정수 $n$에 대해서 $nA \neq B$여야 한다는 뜻이 됩니다. 따라서 원래 문제 그대로 가기보다는 배열을 거꾸로 구성한다고 생각하면 좀 더 접근이 편해집니다. 
 
위의 조건을 이용하면 행렬 점화식 역시 간단하게 얻어낼 수 있습니다. $V_{ij} =$ $i$에서 $j$로 가는 경우의 수라고 놓으면 되기 때문입니다. 
예를 들어 $K=7$이라고 한다면 행렬식 $V$는
 

$ \begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 
\end{bmatrix}  $
 

로 표현이 가능합니다.
이렇게 행렬을 구성해 놓았다면 풀이는 정말 간단합니다. 처음에는 모든 수가 올 수가 있기 때문에 초기 열벡터를 $(1,1,1,...,1,1,1)$로 놓을 수가 있습니다. 이 열벡터를 $x$라고 놓겠습니다. 여기에 $V$를 곱해준다면 $[Vx]_i$는 $N=2$일 때 $i$로 끝나는 경우의 수가 됨을 알 수 있습니다. 따라서 $N=2$라면 $Vx$의 모든 원소들을 합해준게 답이 됩니다.
이걸 확장해본다면 일반적으로 $V^{n-1}x$들의 원소들의 합을 구하면 문제의 답이 됨을 알 수가 있습니다.
 
이 풀이는 굉장히 느립니다. 시간 복잡도를 따져보면 행렬곱에서부터 $K^3$을 요구하기 때문에 단순하게 조건맞춰서 점화식을 돌리는 나이브 DP 보다도 좋을게 없는 풀이입니다. 어떻게 해야 여기서 시간을 더 줄일 수 있을까요?
 
일단 위의 풀이에서 가장 문제되는 것은 행렬곱일테니 행렬곱을 안써도 문제를 풀 수 있게끔 행렬을 분해시켜 봅시다.
위의 행렬 $V$는 밑과 같은 식으로 표현이 됩니다.

$V=J-F$
 

여기서 $J$는 Matrix of ones라고 불리는 행렬로 모든 원소가 $1$인 원소입니다. 즉 다음과 같은 행렬입니다.
 

$ \begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 
\end{bmatrix}  $
 

$F$는 V를 토글시킨 원소입니다. 예를 들어 $K=7$인 경우 다음과 같이 행렬 표현이 됩니다.
 

$ \begin{bmatrix}
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 
\end{bmatrix}  $
 

이제 $V^{n-1}=(J-F)^{n-1}$로 쓸 수 있고 우변을 전개하면 원래 얻고자 했던 값을 얻을 수가 있습니다.
이렇게 행렬을 분해한 뒤에 행렬곱을 진행하면 정말 좋은 성질 몇개를 이용할 수가 있게 됩니다.
 

1. $1$ 이상의 정수 $a$에 대해서 $J^a=k^{a-1}J$가 성립합니다. 이러한 성질 덕분에 $J$가 연속적으로 곱해져있는 경우에는 행렬곱을 진행하지 않아도 됩니다.
2. 임의의 $k \times k$ 행렬 $A$에 대해서 $JAJ = s(A)J$가 성립합니다. 여기서 $s(A)$는 $A$의 모든 원소들의 합을 반환하는 함수입니다.

1번과 2번의 성질을 이용해서 우변을 풀면 항은 $F^pJ, F^p, F^pJF^q, J, JF^p$만 남게 됩니다. ($p$와 $q$는 1 이상의 정수) 또한 F가 홀수개라면 계수가 음수고, 짝수개라면 계수가 양수라는 것도 자명하게 알 수 있습니다.
 
$J$의 좋은 성질 덕분에 이전보다 계산할게 줄었지만 여전히 $F$에 대해서는 행렬곱을 요구합니다. 하지만 $F$ 역시 다음과 같은 좋은 성질을 가지고 있으며 이 풀이의 가장 핵심이 되는 부분입니다.
 

1. $F$는 처음에 대략 $KlogK$개의 $0$이 아닌 원소를 가지고 있으며 $F^2,F^3,...$ 이런식으로 거듭제곱을 진행할 때마다 $0$이 아닌 원소가 절반씩 줄게 됩니다. 이걸 잘 이용하면 행렬곱을 하는 것보다 그냥 인접리스트처럼 생각하고 bfs를 돌리는게 더 효율적으로 $F^a$의 원소들의 합을 구하는 방법이라는걸 알 수가 있습니다.
2. $F$는 nilpotent입니다. 즉 $F$를 여러번 거듭제곱하면 언젠가는 영행렬이 되며 $F^a = O$를 만족하는 $a$는 $\log K$를 넘지 않습니다. $K \leq 50\,000$이므로 대충 어림잡아서 $F$가 연속적으로 20개 정도 곱해져있다면 영행렬이 되어있기 때문에 이런 항들을 더이상 계산해주지 않아도 됩니다!

여전히 항은 $F^pJ, F^p, F^pJF^q, J, JF^p$가 남아있지만, 1번 성질을 이용해서 $s(F),s(F^2),...,s(F^{20})$의 값을 bfs를 통해 제법 빠르게 구해낼 수 있을 뿐만 아니라 2번 성질 덕분에 $F$가 연속적으로 $20$개 이상 붙어있는 항들을 무시할 수 있게 되었습니다. 이제 슬슬 DP를 할 수 있을거 같은 느낌이 듭니다. 관찰을 통해서 좀 더 세세하게 커팅을 해봅시다.
 
우선, $V^{N-1}x$를 따로 구할 필요 없이 그냥 $V^N$의 $1$열의 값들만 봐도 된다는 사실을 알 수 있습니다. $V$의 $1$열이 x랑 동일하기 때문입니다. 이것만 보면 딱히 별거 없어보이지만...
마지막에 $F$가 오는 항의 $1$열의 원소는 전부 다 $0$이다라는 관찰을 한다면 말이 달라집니다. 이 관찰을 이용하면 $JF^p, F^pJF^q$ 역시 무시해도 되는 항이 됩니다. 
 
위의 관찰 덕분에 $J$에서 시작해서 $FJ, JJ, JFJ, FFJ, ...$ 이런식으로 앞에 $J$ 또는 $F$를 붙여나가면서 차수가 $N$인 행렬들을 만들어준 다음에 모든 행렬들을 더해주고 $1$열의 합만 계산해주면 답이 나온다는 결론을 얻어냈습니다. 
 
조금 더 관찰해보면 모든 행렬들을 다 더하고 $1$열의 합을 계산하는게 아니라 처음부터 각각의 행렬들의 $1$열의 합을 구해놓고 그거를 다 더해도 된다는 사실도 알 수 있습니다. 그리고 이러한 관점에서 행렬을 붙여나갔을 때의 상황을 보면
 

1. 앞에 $J$가 붙여질 경우에는 $1$열의 합이 $K$배가 됩니다. 
2. 앞에 $F$가 붙여질 경우에는 바로 이전에 $J$가 왔을 경우에는 $1$열의 합이 $s(F)$배, 그렇지 않고 이전에 $F$가 $p$개 연속으로 붙었을 경우에는 $\frac{s(F^{p+1})}{s(F^p)}$배가 됩니다.

이제 위의 설명을 바탕으로 dp식을 세우면 끝납니다.
 
$dp(i,k) = $ 길이가 $i$고 $F$가 $k$개 연속으로 앞에 붙은 항들을 전부 더한 행렬의 1열의 합이라고 놓으면 다음과 같습니다. 다만, 약간의 편의를 위해서 F가 앞에 붙는 경우에 대해서 살짝 느리게 처리한다고 가정합니다.
 

$dp(1,0) = 1$
$dp(i,0) = K \times  dp(i-1,0) + \sum_{j=1}^{20} s(F^j) \times dp(i-1,j)$
$dp(i,j) = -dp(i-1,j-1)$

 
답은 다음과 같습니다.
 

$ans = K \times  dp(N,0) + \sum_{j=1}^{20} s(F^j) \times dp(N,j)$
 

dp식에서 $F$가 앞에 붙는 경우를 따로 처리해주지 않았기 때문에 답을 내는 과정에서 마지막에 한번 처리해줘야합니다.
 
$s(F), ... , s(F^{20})$를 bfs를 통해 전처리 하는 과정은 대략 $O(Klog K)$가 걸리고 dp식을 전이하는 과정은 $O(NlogK)$가 걸리므로 전체적으로 시간복잡도가 $O(Klog K+NlogK)$ 정도라고 생각해볼 수 있습니다. $N,K$ 둘 다 최대 $50\,000$이므로 해당 시간복잡도에서 충분히 통과가 가능합니다.
 

부록

$s(F), ... , s(F^{20})$를 bfs를 통해 전처리 하는 과정이 $O(Klog K)$인 이유

$K$이하의 수 중에서 $i$의 배수의 개수는 $\frac{K}{i}$개이며 이 값을 $i$를 $1$에서 $K$까지 늘려나가면서 전부 더하면 $\frac{K}{1}+\frac{K}{2}+...+\frac{K}{K} = KlogK$이며 이 값이 $F$의 $0$이 아닌 원소의 개수와 같아집니다. 증명은 조화수열을 적분식으로 고치면 됩니다. 
$F$에서 $F^2$로 가는 과정에서 모든 원소가 적어도 자신의 2배 이상인 값으로 이동한다는 사실은 자명합니다. 따라서 대충 어림 잡아도 $F^2$에서는 $\frac{KlogK}{2}$개의 $0$이 아닌 원소가 있을거라고 짐작이 가능합니다. 이걸 계속 반복해본다면 
$KlogK(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8} + ...)$개의 원소를 확인하는 것이나 마찬가지이며 이 값은 $2KlogK$와 동일하므로 $O(Klog K)$라고 할 수 있습니다.