2016年1月16日 星期六

[HOJ 300][Codechef]Party Invitation

HOJ生病惹QQ,因此我在這裡做了題目備份,請參考~

這題我漏考慮了圖不連通的情況卡了一小時QAQ

假設圖是連通的
先把這張圖當有向圖來看,可以發現,由於每個點最多也只能連一條邊出去,因此整張圖就一定會有一個環,然後旁邊有可能有小樹枝指向這個環(指出去的小樹枝是不可能的,因為這樣環上的點就需要兩條出邊了)
找環的方式很簡單,只要隨便找一個點,順著唯一的有向邊走,當走到重複的一個點時,就可以把這點當環的起點了

先來講點題外話
這題就是要問你一張圖有幾種獨立集
獨立集是甚麼?就是一個點集,在圖上沒有一條邊兩端點都在這個點集裡面

如果題目給的圖是一棵樹,獨立集數量要怎麼算呢?
轉成有根樹後,我們可以使用Dfs+記憶化搜索,令DP[u][c]為根節點為u的這棵子樹的獨立集數量,c=0代表u不能選進獨立集,c=1代表u一定要選進獨立集
因此,我們得到轉移式:
DP[u][0]=Pi{DP[v][0]+DP[v][1],v是u的子節點}(Pi是把每個東西乘起來的結果)
DP[u][1]=Pi{DP[v][0],v是u的子節點}

如果題目給的圖是一個環,獨立集數量要怎麼算呢?
先把環的每個點依序存到CYC裡面
令DP[u][l][r]為從CYC[0~u]裡面選出獨立集的數量,l代表CYC[0]要不要選進獨立集,r代表CYC[u]要不要選進獨立集
一開始,可以先知道DP[0][0][0]和DP[0][1][1]都是1,DP[0][0][1]和DP[0][1][0]都是0
那麼u>0時就可以得到轉移式:
DP[u][l][0]=DP[u-1][l][0]+DP[u-1][l][1]
DP[u][l][1]=DP[u-1][l][0]
最後,答案就是DP[N-1][0][0]+DP[N-1][0][1]+DP[N-1][1][0](N是環的大小)

疑真巧,這題給的圖剛好就是環上面接幾棵樹耶XD
那就來對環作DP吧
先把環的每個點依序存到CYC裡面
為了方便說明,TREE[u][c]代表接到CYC[u]上面的這棵樹裡面選出獨立集的數量,c代表CYC[0]要不要選進獨立集
TREE[u][c]怎麼算上面說過了XD
令DP[u][l][r]為從CYC[0~u]以及「接到這些點上面的樹」裡面選出獨立集的數量,l代表CYC[0]要不要選進獨立集,r代表CYC[u]要不要選進獨立集
一開始,可以先知道DP[0][c][c]是TREE[0][c],DP[0][0][1]和DP[0][1][0]都是0
那麼u>0時就可以得到轉移式:
DP[u][l][0]=TREE[u][0]*(DP[u-1][l][0]+DP[u-1][l][1])
DP[u][l][1]=TREE[u][1]*DP[u-1][l][0]
最後,答案就是DP[N-1][0][0]+DP[N-1][0][1]+DP[N-1][1][0](N是環的大小)

這題實作上沒有甚麼特別複雜的地方,code也很容易寫得出來,傳上去也WA了(?)
咦?
還記的我開頭講甚麼嗎?
這張圖不一定連通!XD

因此,分別將每個連通子圖(可以用並查集判斷)的獨立集數量算出來後,相乘就是答案了(因為它們互相獨立)
喔還有,要記的開long long和模1000000007

code:
#include<cstdio>
#include<cassert>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const LL MOD=1000000007LL;
int DJ[100000];
int Find(const int a){return DJ[a]==a?a:(DJ[a]=Find(DJ[a]));}
int N,M,A[100000];
vector<int>ET[100000];
vector<int>CYC;
bool VIS[100000];
void BuildCYC(const int source)
{
    queue<int>q;
    if(true)
    {
        int cur=source;
        for(;!VIS[cur];cur=A[cur])q.push(cur),VIS[cur]=true;
        while(q.front()!=cur)q.pop();
    }
    CYC.clear();
    while(!q.empty())CYC.push_back(q.front()),q.pop();
    M=CYC.size();
}
LL GetValue_DP[100000][2];
LL GetValue(const int u,const int color)
{
    LL &ans=GetValue_DP[u][color];
    if(ans!=-1LL)return ans;
    ans=1LL;
    for(const int nxt:ET[u])
    {
        const LL ta=GetValue(nxt,0)+(color?0LL:GetValue(nxt,1));
        (ans*=ta)%=MOD;
    }
    return ans;
}
LL Solve(const vector<int>&cyc)
{
    static LL dp[100000][2][2];
    for(int i=0;i<M;i++)for(int j=0;j<4;j++)dp[i][j>>1][j&1]=0LL;
    dp[0][0][0]=GetValue(cyc[0],0);
    dp[0][1][1]=GetValue(cyc[0],1);
    for(int i=0;i+1<M;i++)
    {
        for(int l=0;l<2;l++)for(int r=0;r<2;r++)if(dp[i][l][r]!=0LL)
        {
            const LL &v=dp[i][l][r];
            (dp[i+1][l][0]+=v*GetValue(cyc[i+1],0))%=MOD;
            if(r==0)(dp[i+1][l][1]+=v*GetValue(cyc[i+1],1))%=MOD;
        }
    }
    return (dp[M-1][0][0]+dp[M-1][0][1]+dp[M-1][1][0])%MOD;
}
int main()
{
//    freopen("in.txt","r",stdin);
    int testcase;scanf("%d",&testcase);
    while(testcase--)
    {
        scanf("%d",&N);
        for(int i=0;i<N;i++)ET[i].clear(),DJ[i]=i;
        for(int i=0;i<N;i++)scanf("%d",&A[i]),ET[--A[i]].push_back(i),DJ[Find(A[i])]=Find(i);
        for(int i=0;i<N;i++)for(int j=0;j<2;j++)GetValue_DP[i][j]=-1LL;
        static bool vis[100000];
        for(int i=0;i<N;i++)vis[i]=VIS[i]=false;
        LL ans=1LL;
        for(int i=0;i<N;i++)if(!vis[Find(i)])
        {
            vis[Find(i)]=true;
            BuildCYC(i);
            for(int i=0;i<M;i++)
            {
                vector<int>&s=ET[CYC[(i+1)%M]];
                bool found=false;
                for(auto t=s.begin();t!=s.end();t++)if(*t==CYC[i]){s.erase(t),found=true;break;}
                assert(found);
            }
            (ans*=Solve(CYC))%=MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原