HDU 3441 Rotation(Polya计数 + 数论)
大致题意:总共有A*A个小方格,有C种颜色。你要把着A*A个小方格拆乘K+1个部分,其中K个部分是B*B的正方形,剩下的一个单独的方格。要求着K个大正方形都连着这个单独的小方格成一个圈。现在你要用这C种颜色个小方格染色,使得每一个B*B的正方形内部要在旋转的时候本质不同,然后这个K个大正方形与中间的小方格在旋转的时候也要本质不同。问你本质不同的方案数。
这个比较显然的是一个需要用到两个Polya的题目。首先,这B*B的大正方形内部需要用一个Polya,总共有四种置换,分别对应旋转0°、90°、180°和270°。考虑每种旋转的时候的循环个数,分别是B*B个、(B*B+3)/4个、(B*B+1)/2个和(B*B+3)/4个。然后对于每一个循环个数,用C种颜色去填充,最后除以置换群数目4即可。这个就是对于特定的B,B*B方格的填充方案。我们不妨设这个填充方案是x。
然后就是这K个B*B的格子,在连接中间小个子摆放的时候也要本质不同。那么这个问题,就相当于是一个包含K个珠子的项链,然后去染色也要求旋转的情况下本质不同的问题。但是这里,这个颜色数目,就恰好是我们B*B的格子的填充方案数x。有了这个转换,我们直接按照项链那么去做即可。
注意到本题的数据范围A可以到1e9,那么对应的A*A可以到1e18的级别。然后我们做的时候需要对所有的满足条件的B和K去做,那么满足A*A-1=B*B*K,相当于B*B是A*A-1的因子。但是A*A很大,即使用根号的复杂度求因子也会TLE,所以考虑把A*A-1拆成(A-1)(A+1),然后求A-1和A+1的质因子,两个质因子再合并,之后质因子的组合就是因子。我们用dfs组合质因子,枚举出所有可能的B和K,然后求出x,再当作项链去做。当作项链的时候,也是需要枚举K个的因子,这个因子同样也可以用dfs组合质因子的方式,而且这个质因子恰好就是(A*A-1)/B/B的质因子,即在(A*A-1)的基础上,把B*B的质因子减去。最后求欧拉函数的时候也可以用这个来优化常数。时间复杂度不太好算,大概是?其实我也不知道,反正很快,93ms跑完,具体见代码:
#include<bits/stdc++.h>
#define LL long long
#define mod 1000000007
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define INF 0x3f3f3f3f
#define sf(x) scanf("%d",&x)
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define sc(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr(x,n) memset(x,0,sizeof(x[0])*(n+5))
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace __gnu_pbds;
using namespace std;
const int N = 1e5 + 10;
const LL inv4 = 250000002;
int n,m,sz,tot,ans,ansA,p[N],phi[N],fac[20],a[20];
gp_hash_table<int,int> pri; bool isp[N];
void init()
{
sz=0; phi[1]=1;
for(int i=2;i<N;i++)
{
if (!isp[i]) p[++sz]=i,phi[i]=i-1;
for(int j=1;j<=sz&&p[j]*i<N;j++)
{
int x=i*p[j]; isp[x]=1;
if (i%p[j]==0)
{
phi[x]=phi[i]*p[j]%mod;
break;
} else phi[x]=phi[i]*(p[j]-1);
}
}
}
inline void getp(int x)
{
for(int i=1;p[i]*p[i]<=x&&i<=sz;i++)
{
if (x%p[i]) continue;
int tmp=0;
while(x%p[i]==0) x/=p[i],tmp++;
pri[p[i]]+=tmp;
}
if (x>1) pri[x]++;
}
inline LL qpow(LL x,LL n)
{
LL res=1;
x%=mod; n%=(mod-1);
while(n)
{
if (n&1) res=res*x%mod;
x=x*x%mod; n>>=1;
}
return res;
}
inline LL getphi(LL x)
{
LL res=1,xx=x;
if (x<N) return phi[x];
for(int i=1;i<=tot&&(LL)fac[i]*fac[i]<=x;i++)
{
if (x%fac[i]) continue;
res*=fac[i]-1; x/=fac[i];
while(x%fac[i]==0)
{
x/=fac[i];
res*=fac[i];
}
if (x<N) return res*phi[x]%mod;
}
if (x>1) res*=x-1;
return res%mod;
}
void dfsA(int dep,LL fact,LL x,int c)
{
if (x/fact<fact) return;
if (dep>tot)
{
ansA=(ansA+qpow(c,x/fact)*getphi(fact)%mod)%mod;
if (x/fact!=fact) ansA=(ansA+qpow(c,fact)*getphi(x/fact)%mod)%mod;
return;
}
for(int i=0;i<=a[dep];i++)
{
dfsA(dep+1,fact,x,c);
fact*=fac[dep];
}
}
inline int calA(LL x,int c)
{
int invx=qpow(x,mod-2);
ansA=0; dfsA(1,1,x,c);
return (LL)ansA*invx%mod*m%mod;
}
inline int calB(LL x)
{
int res=qpow(m,x*x);
res=(res+2LL*qpow(m,(x*x+3)/4)%mod)%mod;
res=(res+qpow(m,(x*x+1)/2))%mod;
return res*inv4%mod;
}
void dfsB(int dep,LL fact)
{
if (fact>=n) return;
if (dep>tot)
{
int res=calB(fact);
LL K=((LL)n*n-1)/fact/fact;
ans=(ans+calA(K,res))%mod;
return;
}
int tmp=a[dep];
for(int i=0;i<=tmp;i+=2,a[dep]-=2)
{
dfsB(dep+1,fact);
fact*=fac[dep];
}
a[dep]=tmp;
}
int main()
{
int T,TT=0;
init(); sf(T);
while(T--)
{
pri.clear();
sf(n); sf(m);
ansA=ans=tot=0;
if (n==1)
{
printf("Case %d: %d\n",++TT,m);
continue;
}
getp(n-1); getp(n+1);
for(auto i:pri)
{
fac[++tot]=i.first;
a[tot]=i.second;
}
for(int i=1;i<tot;i++)
for(int j=i+1;j<=tot;j++)
if (fac[i]>fac[j])
{
swap(fac[i],fac[j]);
swap(a[i],a[j]);
}
dfsB(1,1);
printf("Case %d: %d\n",++TT,ans);
}
return 0;
}