Topcoder SRM 711 Div2(hard) TreeMovingDiv2

이 문제는 M개의 트리가 주어지고 각각의 트리에 대해 하나의 엣지를 선택하여

오른쪽 트리에게 주었을때(마지막 트리는 맨 처음 트리에게 준다.) 각 M개의 트리가 여전히 모두 트리가 되도록 간선을 선택하는

모든 경우의 수를 계산하는 문제이다. 

우선 이 문제는 dp 로  풀 수가있다. 그래서 내가 처음 생각해낸 풀이는

dp[i][u][v] : i-1번째 트리에서 엣지 u-v 를 선택했고 i번째 트리부터 엣지들을 잘 선택했을때 M개의 트리가 여전히 트리인 경우의수

이렇게 하면 각각의 트리의 모든 엣지에 대해 없애보고 이전 트리에서 넘겨준 u-v 를 추가했을 때 여전히 트리가 된다면

선택하고 다음트리로 넘어가는 식으로 구현하면 되고 기저 케이스는 M번째 까지 왔을 때 0번째 트리에서 삭제한 엣지를

저장해 두었다가 M번째 트리까지 오면 이 엣지를 실제로 없애보고 이전 트리에서 넘겨준 엣지를 추가해서

트리가 된다면 M개의 트리가 모두 여전히 트리이므로 return 1을 하는 식으로 하면 된다고 생각해서 이렇게 구현을 하였다.

하지만 여기에는 두가지 오류가 있다. 우선 부분문제 자체에 0번째 트리에서 삭제한 엣지에 대한 정보가 정의되어 있지

않기 때문에 이 부분문제는 최적 부분문제를 만족하지 않는다. 그러면 부분문제에 0번째 트리에서 삭제한 엣지에 대한

정보도 포함시켜서 부분문제의 정의를 

dp[i][u][v][u0][v0] : i-1번째 트리에서 엣지 u-v 를 선택했으며 0번째 트리에서 u0-v0를 선택했고 i번째 트리부터 엣지들을 잘 선택했을때 M개의 트리가 여전히 트리인 경우의수

로 하면 풀이 자체는 맞게 된다.

하지만 두번째 문제는 시간 복잡도가 너무 크다는 것이다. 우선 부분 문제는 O(N^5) 이고 각 부분문제를 구하는데 걸리는 시간은

O(N^3) 이다. 부분문제가 O(N^5) 인것은 자명하고, 부분문제를 구하는데 걸리는시간은 엣지를 구성하기 위한 두 노드를

선택하는 모든 정점쌍을 보려면 O(N^2) 의 시간이 들고 엣지가 선택이 되었으면 이 엣지를 실제로 삭제하고 이전 트리에서

넘어온 엣지를 추가해서 여전히 트리가 되는지 확인해야 하는데 이 때 dfs를 돌려야 하기 때문에 O(N) 의 시간이 들게된다.

그래서 총 O(N^8) 의 시간이 걸리게 된다. 50^8은 꽤 크기 때문에 시간안에 돌아갈 수가 없을 것이다.

시간을 줄이기 위해서 알아야 할 것이 몇가지 있다. 우선 트리에서 모든 엣지를 보는데에 걸리는시간은 사실은 O(N^2)가 아니라

O(N) 이다. 왜냐하면 루트노드를 제외한 모든 노드는 하나의 부모를 가지기 때문에 트리의 모든 엣지는 루트를 제외한

각각의 노드로 표현할 수가 있다. 자신과 자신의 부모를 연결하는 엣지를 자신이 대표할 수가 있기 때문이다.

그렇기 때문에 모든 엣지를 검사할 때 O(N) 이 걸리고, 같은 이유로 부분문제에서 엣지를 [u][v] 와 [u0][v0] 처럼 

굳이 하나의 간선을 표현하기 위해 두개의 차원을 사용할 필요가 없다. 그렇기 때문에 부분문제를 새로 정의하자면

p[u] : u의 부모노드

dp[i][u][u0] : i-1번째 트리에서 엣지 u-p[u] 를 선택했으며, 0번째 트리에서 엣지 u0-p[u0] 를 선택했고, i번째 트리부터 엣지들을 잘 선택했을때 M개의 트리가 여전히 트리인 경우의수

이렇게 하면 부분문제의 수는 O(N^3) 가 되고, 각각의 부분문제를 구하는데는 O(N^2) 이 걸리게 된다. 왜냐하면 O(N)로

모든 엣지를 봐주고, 엣지마다 O(N)로 dfs를 돌리기 때문이다. 그렇다면 최종적인 시간 복잡도는 O(N^5) 이다. 하지만 이걸로도

너무 느리다. 한가지 함수를 정의해보자

isStillTree(i,addU,eraseU) : i 번째 트리에서 엣지 eraseU-p[eraseU] 를 삭제하고 엣지 addU-p[addU] 를 추가했을때 여전히 트리인가?

조금만 생각해보면 세 인자가 같은한 이 함수에 대한 답은 같다는 것을 알 수가 있다. 그렇기 때문에 이것을 미리 다 구해놓으면

하나의 부분문제를 구할때 모든 엣지에 대해 dfs를 돌릴 필요가 없이 O(1)에 답을 알 수가 있기 때문에

전체 시간복잡도는 O(N^4) 가 된다. (미리 구하는것은 O(N^4) 에 구할 수가 있다.)

(실제 구현은 미리 구하지는 않았고 그냥 메모이제이션만 하도록했다.)

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi; 
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
class TreeMovingDiv2 {
public:
    ll X[53];
    int G[53][53][53];
    int parent[53][53];
    ll dp[53][53][53];
    int dp2[53][53][53];
    int N,M;
    int visited[53];
    int dfs(int here, int dad, int pos){
        visited[here] = 1;
        FOR(there, N){
            if(!G[pos][here][there] || there == dad) continue;
            if(visited[there]) return 0;
            if(!dfs(there, here, pos)) return 0;
        }
        return 1;
    }
    void dfs2(int here, int dad, int pos){
        for(int there = 0 ; there < N; there++){
            if(!G[pos][here][there] || there==dad) continue;
            parent[pos][there] = here;
            dfs2(there, here, pos);
        }
    }
    int check(int pos, int prevU, int newU){
        int& cache = dp2[pos][prevU][newU];
        if(cache != -1) return cache;
        int prevV = parent[pos][prevU];
        int newV = parent[(pos+M-1)%M][newU];
        G[pos][prevU][prevV] = G[pos][prevV][prevU] = 0;
        int backup = G[pos][newV][newU];
        G[pos][newV][newU] = G[pos][newU][newV] = 1;
        memset(visited,0,sizeof(visited));
        int ret = dfs(0,-1, pos);
        G[pos][newV][newU] = G[pos][newU][newV] = backup;
        G[pos][prevU][prevV] = G[pos][prevV][prevU] = 1;
        FOR(i,N) if(visited[i]==0) ret = false;
        return cache = ret;
    }
    ll go(int pos, int u, int u0){
        ll& cache = dp[pos][u][u0];
        if(cache != -1) return cache;
 
        ll ret = 0;
        if(pos==M){
            if(check(0, u0, u)) return 1;
            return 0;
        }
        for(int i = 0; i < N; i++){
            int p = parent[pos][i];
            if(p == -1) continue;
            if(pos>0 && !check(pos, i, u)) continue;
            (ret += go(pos+1, i, pos?u0:i)) %= MOD;
        }
        return cache = ret;
    }
    void initGraph(vector<int>& roots, vector<int>& a, vector<int>& b, vector<int>& c){
        FOR(i,M) {
            X[0] = c[i];
            REP(k,1,N-2) X[k] = (a[i] * X[k - 1] + b[i]) % MOD;
            REP(j,0,N-2){
                int u = (roots[i] + j + 1) % N;
                int v = (roots[i] + (X[j] % (j+1))) % N;
                G[i][u][v] = G[i][v][u] = 1;
            }
        }
    }
    int count(int n, vector<int> roots, vector<int> a, vector<int> b, vector<int> c) {
        memset(G,0,sizeof(G));
        memset(X,0,sizeof(X));
        memset(parent,-1,sizeof(parent));
        memset(dp,-1,sizeof(dp));
        memset(dp2,-1,sizeof(dp2));
        N = n;
        M = roots.size();
        initGraph(roots, a,b,c);
        for(int i = 0 ; i < M; i++) 
            dfs2(0,-1,i);
 
        return go(0,0,0);
    }
};