某島

… : "…アッカリ~ン . .. . " .. .
August 29, 2010

ZOJ 2612. Stable Sets

Brief description :

給定一個模 r 整數環,子集 A 在多項式 p 下被稱為是穩定的,當且僅當集合中的數字代入 p 以後的運算結果,剛好也是 A 子集。
題目給定兩組多項式 p、q,求同時在 p 和 q 下都穩定的子集的組數。

Analyse :

這個題,不難想像成一個圖論問題,考察多項式 p,對於每一組 (i, p(i)),我們連一條 i 到 p(i) 的
有向邊,於是求一組極小的穩定集等價於圖中的一組強連通分量,如果最後存在 n 個 component,那麼最後的結果不難得到是 2^n。

觀察圖形,發現本題中所有的結點出度都為 1,即由此可以設計出一種簡易的方法求取強連通分量的方法,每次找到一個入度為 0 的點,(則此點不可能在一個環結構類)
用一個隊列和並查集不斷維護即可。另外需要注意的則是需要在 p, q 下保持極小穩定核保持相同,而這種方法則可以方便的將那些已經不可能構成環結構的點丟棄到一個啞類中。(具體此處的實現呢還是有許多值得商討的地方的。)

/*
    Author: xiaodao
    Prog: ZOJ 2612. Stable Sets
    Status: Accepted
    Last modifiy: GMT +8 Aug. 29th 17:49
*/
#include 
#include 
#include 
#include "bignum.h"
using namespace std;
const int N = 101;
int A[N], n; int P[N];
int r; bignum ans;



int Find(int x){
    if ( P[x] != x ) P[x] = Find(P[x]) ;
    return P[x];
}

void Union(int x,int y){
    x = Find(x); y = Find(y);
    if (x < y) P[x] = y ; // # 
    else P[y] = x;
}


int p(int x){
    int res = 0;
    for (int i=n;i>=0;i--)
        res = ((res * x) + A[i]) % r;
    return res;
}

void input(){
    scanf("%d", &n);
    for (int i=n;i>=0;i--)
        scanf("%d", &A[i]);

    int in[N];
    memset(in, 0, sizeof(in));
    for (int i=0;i> r && r>0){
        init(); input(); input(); stat();
        cout << ans << endl;
    }
}