BZOJ 1494: [NOI 2007] 생 성 트 리 개수

이 문 제 는 확실히 비교적 어렵다.
그래서 제 가 문제 풀이 보고 서 를 쓰 는 것 도 가능 한 한 쉬 운 부분 에서 시작 해서 여러분 께 도움 이 되 었 으 면 좋 겠 습 니 다.
제목 링크:http://www.lydsy.com/JudgeOnline/problem.php?id=1494
제목 대의: n (n < = 10 ^ 15) 개의 점 이 있 고 번호 1 ~ n 은 번호 차이 가 k (k < = 5) 의 점 사 이 를 초과 하지 않 아야 연결 할 수 있 으 며 생 성 나무의 종 수 를 물 어 볼 수 있 습 니 다.
알고리즘:
이 문제 의 데이터 범 위 를 보면 상태 압축 을 사용 해 야 한 다 는 것 을 알 수 있다.
우선, 우 리 는 앞의 k 점 의 상 태 를 확정 합 니 다.
각 점 과 그 앞 에 있 는 k 개의 점 의 연결 상황 을 k 비트 2 진수 로 기록 하려 고 했 는데,
그러나 이렇게 처리 할 수 없 는 문 제 는 고리 의 존 재 를 어떻게 배제 하 느 냐 하 는 것 이다.
그래서 문제 풀이 보고 서 를 참고 한 결과 1 ~ n 에서 노드 를 순서대로 처리 할 때
최근 k 개의 점 이 있 는 연결 블록 의 상황 을 k 비트 k 진수 로 기록 합 니 다.
이런 상 태 는 사실 많 지 않다. n = 5 일 때 52 개가 있다.
상태의 번 거 로 움 을 피하 기 위해 서 는 하나의 상태 가 하나의 표현 형식 만 있 음 을 보증 해 야 한다.
이 를 위해 나 는 매우 교묘 한 '최소 표현법' (SOJ 3296) 을 배 웠 다.
그러나 이 문 제 는 최소 표현법 과 는 무관 하 다.
최소 표현법 은 문자열 의 사전 순서 가 가장 작은 순환 표 시 를 구 합 니 다.
본 문제 에 서 는 상 태 를 순환 적 으로 표시 할 수 없 음 이 분명 하 다.
그리고 어느 노드 가 같은 연결 블록 에 있 는 지 알 수 있 는 상황 에서 연결 블록 의 레이 블 을 바 꾸 어 얻 은 상 태 를 최소 화 할 수 있 습 니 다.
우리 가 초기 상 태 를 들 었 을 때 예 를 들 어 노드 1, 2, 3 은 연결 블록 0 에 속 하고 노드 4, 5 는 연결 블록 1 에 속한다.
그렇다면 같은 연결 블록 에는 나 무 를 만 드 는 형태 가 여전히 많다.
뒤의 상태 가 이동 하 는 과정 에서 우 리 는 매 거 진 변 을 통 해 자 연 스 럽 게 이동 할 수 있다.
그러나 초기 상 태 는 이 럴 수 없 었 다. 초기 상태 에 대해 우 리 는 몇 가지 연결 방식 으로 그것 을 얻 을 수 있 는 지 알 수 없 었 다.
이 문 제 는 행렬 을 이용 하여 나무 개 수 를 계산 하 는 방법 (HDOJ 4305) 을 제시 하 였 으 며, 구체 적 으로 는 주 겨울의 을 참고 할 수 있다.
n 개의 점 이 있 는 그림 에 대해 행렬 을 구성 하여:
만약 i = = j, a [i] [j] = dex [i].(dex [i] 는 노드 i 의 도수 이다.
그렇지 않 으 면 점 i 와 점 j 사이 에 가장자리 가 연결 되 어 있 으 면 a [i] [j] = - 1.
끝 없 이 연결 되면 a [i] [j] = 0.
그리고 이 행렬 의 n - 1 단계 주자 식 행렬식 의 절대 값 을 구하 면 이 그림 의 생 성 트 리 개 수 를 얻 을 수 있 습 니 다.
물론 계 산 된 행렬식 의 값 이 매우 크다 면 자 연 스 럽 게 특정한 숫자 에 대해 모형 을 만들어 야 한다 (본 문제 에서 K < = 5, 그 럴 필요 가 없다).
행렬식 모델 의 임 의 값 해법 에 대해 bjin 의 논문 인 에서 소개 했다.
그리고 개인 적 으로 bjin 의 두 문제 가 SPOJ DETER 3 (행렬식 모드) 와 SPOJ MSTS (최소 생 성 트 리 계수, HDOJ 4408 은 이 문제 와 유사),
본제 의 후속 연습 에 매우 적합 하 다.
분명히 이 문제 에 대해 서 는.
인접 K 개 점 중 x 개 점 이 1 번 연결 블록 에 속한다 고 가정 합 니 다.
그러면 이 x 개의 점 중 두 칸 은 반드시 연결 할 수 있 을 것 이다.
우리 가 요구 하 는 것 은 x 개의 점 의 완전 그림 의 생 성 수종 이다.
얻 은 것 은 바로 연결 블록 1 이 현재 K 개 점 이라는 부분 에서 얻 을 수 있 는 생 성 수종 수 입 니 다.
물론, 사실은 정말로 행렬식 을 계산 할 필요 가 없다. 문제 의 시작 부분 은 이미 우리 에 게 n 개 노드 의 완전한 그림 의 생 성 트 리 개 수 는 n ^ (n - 2) 라 고 알려 주 었 다.
이 결론 은 카 일 리 의 정리 로 증명 할 수 있다.
초기 상 태 를 처리 한 후 상태의 전 이 를 살 펴 보 자.
번호 에서 작은 것 부터 큰 것 까지 각 노드 를 처리 하 다.
노드 x 를 처리 할 때마다 k 비트 바 이 너 리 로 이 점 과 그 앞의 k 점 의 연결 상황 을 매 거 집 니 다.
그 다음 에 [x - k - 1, x - 1] 의 원래 상태 에서 [x - k, x] 의 새로운 상태 로 전환 할 수 있다.
물론 이 과정 에서 고리 가 생 길 수 있 습 니 다. 이것 은 집합 을 통 해 판단 할 수 있 습 니 다. 고리 가 생기 면 이 전 이 는 무효 입 니 다.
분명히 노드 순서에 따라 작은 것 부터 큰 것 까지 처리 하고 새로운 연결 블록 을 표시 할 때마다 현재 사용 하지 않 은 최소 레이 블 을 사용 하면 된다.
상태 가 전 이 될 때의 배수 관 계 는 원래 상태 와 새로운 상태 와 만 관련 되 고 점 의 번호 와 는 무관 하 다 는 것 을 알 수 있다.
그래서 우 리 는 초기 벡터 와 전이 행렬 을 구성 할 수 있다.
내 구조의 초기 벡터 g [] 는 행 벡터 이다.모든 위 치 는 초기 상 태 를 대표 한다.
각 위치의 값 은 바로 앞의 k 개 점 에서 몇 가지 연결 방식 이 이런 상 태 를 달성 할 수 있 는 지 하 는 것 이다.
그 다음 에 상태 이동 매트릭스 f [] [] 에 대해 i 행 j 열 은 상태 i 에서 상태 j 로 이동 하 는 데 몇 가지 합 법 적 인 연결 방식 (링 이 되 지 않 고 x - k 점 은 적어도 x - k + 1 ~ x 중의 한 점 과 같은 연결 블록) 이 있 음 을 나타 낸다.
g * pow (f, n - k) 를 구 한 후에 얻 은 행 벡터 의 각 위치 에 대한 수 치 는 이 상태 에 도달 하 는 방법 이 몇 가지 가 있 는 지 를 나타 낸다.
그러나 이런 상태 가 모두 유용 한 것 은 아니다.
모든 점 이 같은 연결 이 빠 른 상태 에 있 는 것 만 유용 하 다. 즉, 상태 0 이다.
그래서 g [0] [0] 을 수출 하면 됩 니 다.
PS：
이 문 제 를 푸 는 과정 에서 유화 정의 논문 인 와 진 단기 의 논문 인 (마침 상기 두 분 도 OI 계 에서 유명한 경기장 부부 로 나무 도 있 고 나무 도 있 습 니 다!), 그리고 ACMonster 와 whjpji 의 문제 풀이 보고 서 를 참고 했다.
대단히 감사합니다!
그리고 적 우 가 아주 길 고 긴 행렬 템 플 릿 을 빌려 주 셔 서 감사합니다.
코드 는 다음 과 같 습 니 다:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

const long long MOD = 65521;
const int MAXK=5,MAXS=60;
int status[MAXS],hash[1<<(3*MAXK)];
int p[MAXK+1],cot[MAXK];
int val[6]= {1,1,1,3,16,125};
long long n;
int k;
int tot;

struct Matrix
{
    int h,w;
    long long mx[MAXS][MAXS];

    Matrix()
    {
        h=0;
        w=0;
        memset(mx,0,sizeof(mx));
    }
    Matrix operator* (const Matrix& b) const
    {
        Matrix tmp;
        memset(tmp.mx,0,sizeof(tmp.mx));
        tmp.h=h;
        tmp.w=b.w;
        for (int i=0; i<h; i++)
        {
            for (int j=0; j<b.w; j++)
            {
                for (int k=0; k<w; k++)
                {
                    tmp.mx[i][j]=(tmp.mx[i][j]+(mx[i][k]*b.mx[k][j])%MOD)%MOD;
                }
            }
        }
        return tmp;
    }

    void initE()
    {
        memset(mx,0, sizeof(mx));
        for (int i=0 ; i<w ; i++)
        {
            mx[i][i]=1LL;
        }
    }

    Matrix mpow(long long  k)
    {
        Matrix c,b;
        c=(*this);
        memset(b.mx,0,sizeof(b.mx));
        b.w=w;
        b.h=h;
        b.initE();
        while(k)
        {
            if(k&1LL)
            {
                b=b*c;
            }
            c=c*c;
            k>>=1LL;
        }
        return b;
    }
};
Matrix g,f;

void dfs(int mask, int dep)
{
    if(dep==k)
    {
        g.mx[0][tot]=1;
        memset(cot,0,sizeof(cot));
        for(int i=0; i<k; i++)
        {
            cot[mask>>(i*3)&7]++;
        }
        for(int i=0; i<k; i++)
        {
            g.mx[0][tot]*=val[cot[i]];
        }
        status[tot]=mask;
        hash[mask]=tot++;
        return;
    }
    int tmp=-1;
    for(int i=0; i<dep; i++)
    {
        tmp=max(tmp,mask>>(i*3)&7);
    }
    for(int i=0; i<=tmp+1&&i<k; i++)
    {
        dfs(mask<<3|i,dep+1);
    }
}

int findp(int x)
{
    return p[x]==-1?x:p[x]=findp(p[x]);
}

int justify()
{
    bool vis[MAXK];
    memset(vis,0,sizeof(vis));
    int tot=0;
    int mask=0;
    for(int i=k-1; i>=0; i--)
    {
        if(!vis[i])
        {
            vis[i]=true;
            mask|=tot<<(i*3);
            for(int j=i-1; j>=0; j--)
            {
                if(findp(i+1)==findp(j+1))
                {
                    vis[j]=true;
                    mask|=tot<<(j*3);
                }
            }
            tot++;
        }
    }
    return hash[mask];
}

void cal(int s, int mask)
{
    memset(p,-1,sizeof(p));
    for(int i=0; i<k; i++)
    {
        for(int j=i+1; j<k; j++)
        {
            if((status[s]>>(i*3)&7)==(status[s]>>(j*3)&7))
            {
                int px=findp(i);
                int py=findp(j);
                if(px!=py)
                {
                    p[px]=py;
                }
            }
        }
    }
    for(int i=0; i<k; i++)
    {
        if((mask>>i)&1)
        {
            int px=findp(i);
            int py=findp(k);
            if(px==py)
            {
                return;
            }
            p[px]=py;
        }
    }
    bool flg=false;
    for(int i=1; i<=k; i++)
    {
        if(findp(i)==findp(0))
        {
            flg=true;
            break;
        }
    }
    if(!flg)
    {
        return;
    }
    f.mx[s][justify()]++;
}

int main()
{
    while(scanf("%d%lld",&k,&n)==2)
    {
        memset(f.mx,0,sizeof(f.mx));
        memset(g.mx,0,sizeof(g.mx));
        tot=0;
        dfs(0,0);
        g.h=1;
        g.w=f.w=f.h=tot;
        for(int i=0; i<tot; i++)
        {
            for(int mask=0; mask<(1<<k); mask++)
            {
                cal(i,mask);
            }
        }
        g=g*f.mpow(n-k);
        printf("%lld
",g.mx[0][0]);
    }
    return 0;
}