[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;
}