正文

【THUSC2017】【LOJ2981】如果奇迹有颜色 DP BM 打表 线性递推

IP云
IP云V管理员/0 阅读
12/01
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目大意

有一个 \(n\) 个点的环，你要用 \(m\) 中颜色染这 \(n\) 个点。

要求连续 \(m\) 个点的颜色不能是 $1 \sim m $ 的排列。

两种环相同当且仅当这两个环可以在旋转之后变得一模一样。

求方案数对 \({10}^9+7\) 取模的结果。

\(n\leq {10}^9,m\leq 7\)

题解

考虑 polya 定理，记 \(f(n)\) 为 \(n\) 个点的答案，\(g(n)\) 为 \(n\) 个点不考虑旋转的答案。那么就有

\[\begin{align}
f(n)&=\frac{1}{n}\sum_{i=1}^ng(\gcd(n,i))\\
&=\frac{1}{n}\sum_{i\mid n}\varphi(\frac{n}{i})g(i)
\end{align}
\]

\(g(i)\) 可以 DP 计算。

记 \(h_{i,j,k}\) 为长度为 \(i\) 的链，前 \(m\) 个点的状态（颜色）为 \(j\)，最后 \(m\) 个点的状态为 \(k\) 的方案数。

还可以记录前 \(m\) 个颜色的前多少个是互不相同的，还有最后 \(m\) 个点的颜色。就前 \(j\) 个的颜色是互不相同的，第 \(j+1\) 个点颜色和前面某个点颜色相同。

显然 \(g(i)\) 有一个长度不超过 \(m^m\) 的递推式。

暴力打出前面的项然后 BM 求出递推式即可。

开 O2 只用了 48s 就打出来了。

\(m=7\) 时递推式长度为 \(409\)。

表在这：https://github.com/ywwywwyww/THUSC2017/tree/master/yww/farben

代码 
const int N=1010;

const ll p=1000000007;

ll fp(ll a,ll b)

{

	ll s=1;

	for(;b;b>>=1,a=a*a%p)

		if(b&1)

			s=s*a%p;

	return s;

}

ll b[10][2010]=表;

ll a[10][2010]=表;

int c[N],d[N],t;

ll pw[N][N];

ll ans;

int n,m;

int s[N];

int len;

void add(int &a,ll b)

{

	a=(a+b)%p;

}

void mul()

{

	static int f[N];

	for(int i=0;i<=2*len;i++)

		f[i]=0;

	for(int i=0;i<=len;i++)

		if(s[i])

			for(int j=0;j<=len;j++)

				add(f[i+j],(ll)s[i]*s[j]);

	for(int i=0;i<=2*len;i++)

		s[i]=f[i];

}

void module()

{

	for(int i=2*len;i>=len;i--)

		if(s[i])

		{

			for(int j=1;j<=len;j++)

				add(s[i-j],(ll)s[i]*b[m][j]);

			s[i]=0;

		}

}

void fp(int x)

{

	if(!x)

	{

		for(int i=0;i<=2*len;i++)

			s[i]=0;

		s[0]=1;

		return;

	}

	fp(x>>1);

	mul();

	if(x&1)

	{

		for(int i=2*len;i>=1;i--)

			s[i]=s[i-1];

		s[0]=0;

	}

	module();

}

ll calc(int x)

{

	if(x<=500)

		return a[m][x];

	fp(x-1);

	ll res=0;

	for(int i=1;i<=len;i++)

		res=(res+(ll)a[m][i]*s[i-1])%p;

	return res;

}

void dfs(int x,int y,ll phi)

{

	if(x>t)

	{

		ans=(ans+calc(y)*phi)%p;

		return;

	}

	for(int i=0;i<d[x];i++)

		dfs(x+1,y*pw[x][i],phi*(c[x]-1)%p*pw[x][d[x]-i-1]%p);

	dfs(x+1,y*pw[x][d[x]],phi);

}

int main()

{

	open("farben");

	scanf("%d%d",&n,&m);

	int _n=n;

	for(int i=2;i*i<=_n;i++)

		if(_n%i==0)

		{

			c[++t]=i;

			while(_n%i==0)

			{

				d[t]++;

				_n/=i;

			}

		}

	if(_n>1)

	{

		c[++t]=_n;

		d[t]=1;

	}

	for(int i=1;i<=t;i++)

	{

		pw[i][0]=1;

		for(int j=1;j<=d[i];j++)

			pw[i][j]=pw[i][j-1]*c[i]%p;

	}

	len=b[m][0];

	dfs(1,1,1);

	ans=ans*fp(n,p-2)%p;

	ans=(ans%p+p)%p;

	printf("%lld\n",ans);

	return 0;

}

打表程序 

const ll p=1000000007;

const int N=1010;

const int n=1000;

//const int m=5;

int m;

ll fp(ll a,ll b)

{

	ll s=1;

	for(;b;b>>=1,a=a*a%p)

		if(b&1)

			s=s*a%p;

	return s;

}

const int MA=2100000;

int e[MA];

int ban[MA];

vector<int> g[N];

int pw[N];

int ma;

namespace gao1

{

	int a[N],b[N],c[N];

	void dfs(int x)

	{

		if(x>m)

		{

			for(int i=1;i<=m;i++)

				b[i]=0;

			int tot=0;

			int s=0;

			int s2=0;

			int first=0;

			for(int i=1;i<=m;i++)

			{

				if(!b[a[i]])

					b[a[i]]=++tot;

				c[i]=b[a[i]];

				s+=c[i]*pw[i-1];

				s2+=a[i]*pw[i-1];

				if(c[i]<=c[i-1]&&!first)

					first=i-1;

			}

			if(tot==m)

				ban[s2]=1;

			else

				g[first].push_back(s);

			return;

		}

		for(int i=1;i<=m;i++)

		{

			a[x]=i;

			dfs(x+1);

		}

	}

	void gao()

	{

		dfs(1);

	}

}

namespace gao2

{

	int a[N],b[N],c[N];

	void dfs(int x)

	{

		if(x>m)

		{

			for(int i=1;i<=m;i++)

				b[i]=0;

			for(int i=m;i>=1;i--)

				if(!a[i]||!b[a[i]])

				{

					c[i]=a[i];

					b[a[i]]=1;

				}

				else

					c[i]=0;

			int s=0,s1=0;

			for(int i=1;i<=m;i++)

				s+=c[i]*pw[i-1];

			for(int i=1;i<=m;i++)

				s1+=a[i]*pw[i-1];

			e[s1]=s;

			return;

		}

		for(int i=0;i<=m;i++)

		{

			a[x]=i;

			dfs(x+1);

		}

	}

	void gao()

	{

		dfs(1);

	}

}

int f[N];

int h[2][MA];

int d[MA];

void add(int &a,int b)

{

	a=(a+b)%p;

}

int append(int a,int b)

{

	return a/(m+1)+b*pw[m-1];

}

namespace gao3

{

	void gao(int x)

	{

		memset(d,0,sizeof d);

		for(int i=0;i<=ma;i++)

		{

			int flag=1;

			for(int y=i,j=1;j<=x;j++)

			{

				y=append(y,j);

				if(ban[y])

				{

					flag=0;

					break;

				}

			}

			d[i]=flag;

		}

		memset(h,0,sizeof h);

		int cur=0;

		for(auto v:g[x])

			h[cur][e[v]]++;

		for(int i=m;i<=n;i++)

		{

			fprintf(stderr,"%d %d %d\n",m,x,i);

			memset(h[cur^1],0,sizeof h[cur^1]);

			for(int j=0;j<=ma;j++)

				if(h[cur][j]&&!ban[j])

				{

					add(f[i],d[j]*h[cur][j]);

					for(int k=1;k<=m;k++)

						add(h[cur^1][e[append(j,k)]],h[cur][j]);

				}

			cur^=1;

		}

	}

}

int main(int argc,char **argv)

{

//	freopen("farben2.txt","w",stdout);

	sscanf(argv[1],"%d",&m);

	ma=fp(m+1,m);

	pw[0]=1;

	for(int i=1;i<=m;i++)

		pw[i]=pw[i-1]*(m+1);

	gao1::gao();

	gao2::gao();

	for(int i=1;i<m;i++)

		f[i]=fp(m,i);

	for(int i=1;i<m;i++)

		gao3::gao(i);

	for(int i=1;i<=n;i++)

		printf("%d\n",f[i]);

	return 0;

}

相关阅读

目录[+]