Atcoder Grand Contest 007&008

Next or Nextnext

题目描述

点此看题

解法

做这道题真的太难受了，理解起来困难，代码细节写错，不知道花了多少时间\(...\)

首先把题目限制做一个转化，我们使用经典建图 \(i\rightarrow p_i\)，那么建出来一定是若干个环，并且每个点在环上跳一步或者跳两步可以到达 \(a_i\)，我们称之为答案图。

为了更充分的思考 \(a_i\) 的限制我们建出限制图，也就是 \(i\rightarrow a_i\) 的图，我们综合思考这两个图。考虑限制图是一棵基环内向树，但是如果我们从答案图的角度去构建限制图，每条边在环上的距离都 \(\leq 2\)，所以只有这些情况：

• 如果答案图的长度是偶数，那么限制图可以原封不动，或者分裂成两个长度相等的环（都跳两步）
• 如果答案图的长度是奇数，那么限制图可以原封不动，或者变成另一个环（都跳两步，非自环）
• 有可能把限制图构建成无分岔的基环内向树（因为只能跳一步或者两步，所以一旦有分叉环就接不上）

因为现在我们只知道限制图，所以我们通过上述情况还原答案图来计数：

• 对于不存在支链的环：可以把两个长度相同的环拼起来；可以单独还原一个环，如果环是奇数且非自环，则有单独弄有两种情况；否则只能原封不动。这里可以通过简单 \(dp\) 实现（决策是拼起来还是自己搞）
• 对于存在支链的环，可以看下图：

设 \(lspace\) 表示上一个支链的根到这个支链的根的距离（特别地，如果只有一个支链那么 \(lspace=n\)），\(ltree\) 表示这个支链的长度，两种情况分别是在根前面放支链的节点或者是放环上的节点，那么方案数是 \([lspace\geq ltree]+[lspace>ltree]\)，判断方案可不可行的方法就是看够不够把支链塞到环里面。

总结

双图策略可以帮助你充分考虑已知信息和所求，通过思考图的关系来发现问题性质。

#include 
#include 
#include 
using namespace std;
const int M = 100005;
const int MOD = 1e9+7;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,tot,ans,f[M],a[M],b[M],c[M],vis[M],dep[M];
struct edge{int v,next;}e[M];
void dfs(int u)
{
	dep[u]=1;int ls=0;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(vis[v]==2) continue;
		if(ls) {puts("0");exit(0);}
		ls=1;dfs(v);dep[u]=dep[v]+1;
	}
}
signed main()
{
	n=read();ans=1;
	for(int i=1;i<=n;i++)
	{
		a[i]=read();//i->a[i]
		e[++tot]=edge{i,f[a[i]]},f[a[i]]=tot;//a[i]->i
	}
	for(int i=1;i<=n;i++) if(!dep[i])
	{
		int t=0,x=i,lst=1;
		for(;!vis[x];x=a[x]) vis[x]=1;
		for(;vis[x]==1;x=a[x]) vis[x]=2,c[++t]=x;
		for(int j=t;j>=1;j--)
		{
			dfs(c[j]);
			if(lst==1 && dep[c[j]]!=1) lst=j-t;
		}
		if(lst==1) {b[t]++;continue;}
		for(int j=1;j<=t;j++) if(dep[c[j]]>1)
		{
			int ls=j-lst,lt=dep[c[j]]-1;
			if(lslt) ans=ans*2%MOD;
			lst=j;
		}
	}
	for(int i=1;i<=n;i++) if(b[i])
	{
		int lst=0,now=1,nxt=0;
		for(int j=1;j<=b[i];j++)
		{
			nxt=((i&1)&&i!=1)?(now<<1):now;
			nxt=(nxt+(j-1)*lst%MOD*i)%MOD;
			lst=now;now=nxt;
		}
		ans=ans*now%MOD;
	}
	printf("%lld\n",ans);
}