CC BY 4.0 （except where otherwise noted or for reposted articles）
뭔가 DP문제들만 올리는 기분이네…
문제
3인팀에서 $N$개의 문제를 특정 조건들에 맞게 배분하는 경우의 수 ($\mod 10^9+7$)
풀이
조건들을 살펴보자.
- A가 해결한 문제의 수는 $K$의 배수가 되어야 한다.
- B는 문제를 연속해서 풀 수 없다.
- C는 한 문제 이상 해결해야 한다.
조건들을 이대로 하나의 변수로 관리하기는 너무 어려워 보인다. A, B, C에 대한 조건을 나눠서 생각해보자.
A - 해결한 문제의 수는 $K$의 배수가 되어야 한다는 결국 $\mod K$ 가 0이여야 한다는 뜻이니 A가 푼 문제 수 $\mod K$를 하나의 변수로 관리하자.
B - B는 연속으로 문제를 해결할 수 없다. 이는 단순히 B가 i번 문제를 해결하는 경우를 고려 할 때 $i-1$번 문제를 A나 C가 해결한 경우만 고려해주면 된다.
C - C는 한 문제 이상 해결해야 한다. 따라서 C는 문제를 풀은적이 있냐 없냐만 중요하니 이를 변수로 관리한다.
하지만 아직도 문제를 이대로 풀기에는 어렵다. B같은 조건을 고려하면 이전 문제를 누가 풀었는지가 중요하기 때문이다.
따라서 $i$ 번째 문제를 A가 푼 경우, B가 푼 경우 C가 푼 경우를 각각 별개의 점화식으로 관리해준다.
이제 C가 문제를 풀었는지 안 풀었는지에 대한 정보를 변수 $j$로 나타내고 ($0$ 또는 $1$) A가 푼 문제 수 $\mod K$를 $k$라는 변수로 나타내면 A가 i번째 문제를 푸는 경우를 $A_{i, j, k}$라고 써볼 수 있다. 비슷하게 B와 C에 대해서도 적용해주면 답은 $A_{N, 1, 0} + B_{N, 1, 0} + C_{N, 1, 0}$이 된다.
상태를 정의 했으니 전이를 생각해보자. 다소 복잡한 면이 있긴 하지만 어렵진 않다.
\[A_{i, 0, k} = A_{i-1, 0, ((k - 1) + K) \mod K} + B_{i-1, 0, ((k - 1) + K) \mod K}\] \[A_{i, 1, k} = A_{i-1, 1, ((k - 1) + K) \mod K} + B_{i-1, 1, ((k - 1) + K) \mod K} + C_{i-1, 1, ((k - 1) + K) \mod K}\]A가 문제를 푼다면 $k$에 변화가 생긴다. $i-1, j, k-1$에 해당하는 경우들을 더해준다. 나머지이기 때문에 음수일 때 처리에 주의하고 $j$ 값에 따라 $C$를 포함할지 말지 여부를 결정한다.
\[B_{i, 0, k} = A_{i-1, 0, k}\] \[B_{i, 1, k} = A_{i-1, 1, k} + C_{i-1, 1, k}\]B는 연속으로 문제를 풀 수 없으니 B는 포함되지 않는다. 추가로 $j$가 $0$일 때는 C도 포함되지 않는다.
\[C_{i, 1, k} = A_{i-1, 0, k} + A_{i-1, 1, k} + B_{i-1, 0, k} + B_{i-1, 1, k} + C_{i-1, 1, k}\]C가 문제를 풀 때는 $j$가 무조건 $1$이다.
이제 이걸 전부 코드로 옮기면 된다… 만 $K$가 $0$일 수도 있다. 이 경우 A는 문제를 풀면 안되니 별개로 처리해줘야 한다. 여기까지 조심했다면 문제를 해결 가능하다. 어떻게 처리해야 하는지는 left as an exercise to the reader이다. 아래 코드에 나와 있으니 참고해도 좋다.
코드 (C++)
ll N, K;
// up-to ith, used C?, A mod K
ll A[100005][2][10];
ll B[100005][2][10];
ll C[100005][2][10];
// if K==0, up-to ith, used C?
ll B2[100005][2];
ll C2[100005][2];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> N >> K;
if(N==1){
cout << 1;
}
else if(K==0){
B2[1][0] = 1; C2[1][1] = 1;
for(int i=2; i<=N; i++){
B2[i][1] = C2[i-1][1];
C2[i][1] = B2[i-1][0] + B2[i-1][1] + C2[i-1][1];
B2[i][1] %= MOD;
C2[i][1] %= MOD;
}
cout << ((B2[N][1])%MOD + (C2[N][1])%MOD)%MOD;
}
else{
for(int i=0; i<K; i++){
A[1][0][i] = ((i==1 || K==1) ? 1 : 0);
B[1][0][i] = (i==0 ? 1 : 0);
C[1][1][i] = (i==0 ? 1 : 0);
}
for(int i=2; i<=N; i++){
for(int k=0; k<K; k++){
A[i][0][k] =
A[i-1][0][((k-1)+K)%K] +
B[i-1][0][((k-1)+K)%K];
A[i][1][k] =
A[i-1][1][((k-1)+K)%K] +
B[i-1][1][((k-1)+K)%K] +
C[i-1][1][((k-1)+K)%K];
B[i][0][k] =
A[i-1][0][k];
B[i][1][k] =
A[i-1][1][k] + C[i-1][1][k];
C[i][1][k] =
A[i-1][0][k] + A[i-1][1][k] +
B[i-1][0][k] + B[i-1][1][k] +
C[i-1][1][k];
A[i][0][k] %= MOD;
A[i][1][k] %= MOD;
B[i][0][k] %= MOD;
B[i][1][k] %= MOD;
C[i][0][k] %= MOD;
C[i][1][k] %= MOD;
}
}
cout << ((A[N][1][0]%MOD) +
(B[N][1][0] % MOD) +
(C[N][1][0] % MOD)) % MOD;
}
}
Large version (팀 연습 더 /<18289>)
눈치챈 사람도 있겠지만 점화식이 전부 선형 점화식이다. 따라서 행렬의 빠른 거듭 제곱으로 $N$번째 값을 빠르게 계산할 수 있으며 이것만 적용하면 문제가 풀린다.
코드 Large version (C++)
struct Matrix{
int N, M; vector<vector<ll>>Mat;
Matrix(int n, int m){
N = n; M = m;
Mat.resize(n, vector<ll>(M, 0));
}
Matrix operator*(const Matrix& rhs) const{
assert( M == rhs.N ); Matrix ret(N, rhs.M);
for(int i=0; i<N; i++){
for(int j=0; j<rhs.M; j++){
for(int k=0; k<M; k++){
ret.Mat[i][j] += (Mat[i][k] * rhs.Mat[k][j]) % MOD;
ret.Mat[i][j] %= MOD;
}
}
}
return ret;
}
Matrix ID(){
assert(N == M); Matrix I(N, N);
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
I.Mat[i][j] = 1;
}
}
return I;
}
Matrix exp(ll k){
if(k==0){
return ID();
}
if(k==1){
return *this;
}
Matrix ret = exp(k/2);
ret = ret * ret;
if(k % 2 == 0) return ret;
else return ret * (*this);
}
};
ll N, K;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> N >> K;
if(N==1){
cout << 1;
}
else if(K==0){
//B2 B2' C2
Matrix res(3, 1);
res.Mat[1][0] = 1, res.Mat[2][0] = 1;
Matrix m(3, 3);
m.Mat[0][2] = m.Mat[2][0] = m.Mat[2][1] = m.Mat[2][2] = 1;
N -= 1;
Matrix ret = m.exp(N) * res;
cout << (ret.Mat[0][0] + ret.Mat[2][0])%MOD;
}
else{
// A0 ... Ak-1 A'0 ... A'k-1 B0 .. Bk-1 B'0 ... B'k-1 C0 ... Ck-1
Matrix res(5*K, 1); Matrix m(5*K, 5*K);
for(int i=0; i<K; i++){
res.Mat[K + i][0] = ((i==1 || K==1) ? 1 : 0);
res.Mat[K*3 + i][0] = (i==0 ? 1 : 0);
res.Mat[K*4 + i][0] = (i==0 ? 1 : 0);
}
//A
for(int i=0; i<K; i++){
m.Mat[i][((i-1)+K)%K] = 1;
m.Mat[i][2*K +((i-1)+K)%K] = 1;
m.Mat[i][4*K +((i-1)+K)%K] = 1;
}
//A'
for(int i=0; i<K; i++){
m.Mat[K+i][K+((i-1)+K)%K] = 1;
m.Mat[K+i][3*K +((i-1)+K)%K] = 1;
}
//B
for(int i=0; i<K; i++){
m.Mat[2*K+i][i] = 1;
m.Mat[2*K+i][4*K + i] = 1;
}
//B'
for(int i=0; i<K; i++){
m.Mat[3*K+i][K+i] = 1;
}
//C
for(int i=0; i<K; i++){
m.Mat[4*K+i][i] = m.Mat[4*K+i][K+i] = m.Mat[4*K+i][2*K+i] = m.Mat[4*K+i][3*K+i] = m.Mat[4*K+i][4*K+i] = 1;
}
N -= 1;
Matrix ret = m.exp(N) * res;
cout << (ret.Mat[0][0] + ret.Mat[2*K][0] + ret.Mat[4*K][0])%MOD;
}
}