讨论 / noi 2007 生成树计数 求标程
522526392 2011-10-04 01:27:00
点我顶贴 收藏 删除
寻求标程,c,pascal均可
#1 wwwaaannngggrs@2011-10-04 01:27:00
回复 删除
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <map>

#define GET(S, i) ((S >> (i + i + i)) & 7)

#define CHA(S, i, t) (S ^ ((GET(S, i) ^ t) << (i + i + i)))

#define DEBUG

using namespace std;

const int MO = 65521;

long long n;

int k;

int calcS, nowS, nownum;

struct Thash{

map<int, int> M; int tot;

int find(int t)

{

if (M.count(t) > 0) return M[t];

else return M[t] = ++tot;

}

} H;

inline int mul(int a,int b) {

int ret;

__asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n"

:"=d"(ret):"a"(a),"b"(b),"c"(MO));

return ret;

}

struct Tmatrix{

int data[71][71];

int r, c;

void clear() { memset(data, 0, sizeof(data)); }

}TM, temp, start, G;

inline Tmatrix operator * (Tmatrix A, Tmatrix B)

{

temp.r = A.r; temp.c = B.c;

for (int i = 1; i <= temp.r; i++)

for (int j = 1; j <= temp.c; j++){

temp.data[i][j] = 0;

for (int k = 1; k <= A.c; k++)

temp.data[i][j] = (temp.data[i][j] + mul(A.data[i][k], B.data[k][j]) ) % MO;

}

return temp;

}

int app[10];

int findnew(int S)

{

for (int i = 0; i <= 7; i++) app[i] = false;

for (int i = 0; i <= k; i++) app[GET(S, i)] = true;

for (int i = 0; i <= 7; i++) if (!app[i]) return i;

return 0;

}

int newnum[101];

int rebuild(int S, int flag = false)

{

int tot = -1;

for (int i = 0; i <= 7; i++) newnum[i] = -1;

for (int i = 0; i <= k - flag; i++){

int t = GET(S, i);

if (newnum[t] == -1) newnum[t] = ++tot;

}

for (int i = 0; i <= k - flag; i++) S = CHA(S, i, newnum[GET(S, i)]);

return S;

}

int merge(int S, int a, int b)

{

a = GET(S, a); b = GET(S, b);

for (int i = 0; i <= k; i++) if (GET(S, i) == a) S = CHA(S, i, b);

return rebuild(S);

}

bool check(int S)

{

return rebuild(S) == S;

}

void checkDFS()

{

int S = rebuild(nowS);

bool bad = true;

for (int i = 1; i <= k; i++) if (GET(S, i) == GET(S, 0)) bad = false;

if (bad) return;

int nS = rebuild(S >> 3, true);

TM.data[nownum][H.find(nS)]++;

}

void DFS(int dep)

{

if (dep == k) { checkDFS(); return; }

DFS(dep + 1);

if (GET(nowS, k) == GET(nowS, dep)) return;

int tempS = nowS;

nowS = merge(nowS, dep, k);

DFS(dep + 1);

nowS = tempS;

}

int calcstart(int S)

{

for (int i = 0; i <= 7; i++) app[i] = 0;

for (int i = 0; i < k; i++) ++app[GET(S, i)];

int t = 1;

for (int i = 0; i <= 7; i++) if (app[i] > 2)

for (int j = 1; j <= app[i] - 2; j++)

t = t * app[i];

return t;

}

void prepare()

{

for (int i = 0; i <= ((1 << (k * 3)) - 1); i++) if (check(i)){

nownum = H.find(i); calcS = nowS = i;

int t = findnew(nowS); nowS = CHA(nowS, k, t);

t = nownum;

start.data[1][t] = calcstart(i);

DFS(0);

}

}

int main()

{

freopen("count.in", "r", stdin); freopen("count.out", "w", stdout);

cin >> k >> n;

prepare();

TM.r = TM.c = H.tot;

start.r = 1; start.c = H.tot;

G = TM;

for (long long i = n - k - 1; i; i >>= 1){

if (i & 1) G = G * TM;

TM = TM * TM;

}

start = start * G;

printf("%d\n", start.data[1][1]);

}

查看更多回复
提交回复