[JSOI2011]同分异构体计数

C++14(g++5.4) 解法, 执行用时: 832ms, 内存消耗: 816K, 提交时间: 2020-02-19 09:42:26

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1010
#define maxm 55
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-0x30;
    return f*x;
}
ll f[maxn], f2[maxn], f3[maxn], g[maxn], N, M, inv[maxn], mod, dp[maxm][maxn];
ll fastpow(ll a, ll b, ll c)
{
    ll t(a%c), ans(1ll);
    for(;b;b>>=1,t=t*t%c)if(b&1)ans=ans*t%c;
    return ans;
}
int main()
{
    ll i, j, k, n=read(), m=read();
    mod=read();
    inv[1]=1;for(int i=2;i<maxn;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    f[0]=f2[0]=f3[0]=1;
    rep(i,1,n)
    {
        f[i]=f3[i-1];
        for(j=0;2*j<=i-1;j++)(f[i]+=3*f[j]*f[i-1-2*j])%=mod;
        if((i-1)%3==0)(f[i]+=2*f[(i-1)/3])%=mod;
        (f[i]*=inv[6])%=mod;

        g[i]=f2[i-1];
        if((i-1)%2==0)(g[i]+=f[i-1>>1])%=mod;
        (g[i]*=inv[2])%=mod;

        for(j=0;j<=i;j++)(f2[i]+=f[j]*f[i-j])%=mod;
        for(j=0;j<=i;j++)(f3[i]+=f[j]*f2[i-j])%=mod;

        // printf("f[%lld]=%lld g=%lld\n",i,f[i],g[i]);
    }
    dp[0][0]=1;
    rep(i,1,m)rep(j,1,n)rep(k,1,j)(dp[i][j]+=dp[i-1][j-k]*g[k])%=mod;
    ll ans=0, tot=0;
    rep(i,3,m)
    {
        // printf("i=%lld\n",i);
        ll tmp=0;
        rep(j,0,i-1)
        {
            ll cnt=__gcd(j,i), sz=i/cnt;
            if(n%sz==0)tmp += dp[cnt][n/sz];
            tmp %= mod;
            // printf("        j=%lld tmp=%lld cnt=%lld sz=%lld dp=%lld\n",j,tmp,cnt,sz,dp[cnt][n/sz]);
        }
        // printf("    tmp=%lld tot=%lld\n",tmp,tot);
        // de(tmp), de(tot);
        if(i%2==0)
        {
            for(j=1;j<=n;j++)for(k=1;j+k<=n;k++)
            {
                if((n-j-k)%2!=0)continue;
                tmp += (dp[1][j]*dp[1][k]%mod*dp[(i-2)/2][(n-j-k)/2]%mod*(i>>1))%mod;
                tmp %= mod;
            }
            if(n%2==0)
            {
                tmp += dp[i>>1][n/2]*(i>>1);
                tmp %= mod;
            }
        }
        if(i%2==1)
        {
            for(j=1;j<=n;j++)
            {
                if((n-j)%2==0)tmp += (dp[1][j]*dp[(i-1)/2][n-j>>1]%mod*i)%mod;
                // printf("        j=%lld tmp=%lld\n",j, tmp);
                tmp %= mod;
            }
        }
        // de(tmp), de(tot);
        tmp = tmp*fastpow(2*i,mod-2,mod) %mod;
        ( ans += tmp ) %=mod;
        // printf("    ans=%lld add=%lld\n",ans,tmp);
    }
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 627ms, 内存消耗: 872K, 提交时间: 2020-03-08 23:16:57

#include<cstdio>
typedef unsigned long long u64;
typedef unsigned int u32;
int n,m;
u32 P;
int gcd(int a,int b)
{
	for(int c;b;c=a,a=b,b=c%b);
	return a;
 } 
 int phi(int n)
 {
 	int v=n;
 	for(int i=2;i*i<=n;++i)
 	if(n%i==0)
 	{
 		do n/=i;while(n%i==0);
 		v=v/i*(i-1);
	 }
	 if(n>1) v=v/n*(n-1);
	 return v;
 }
 inline u32 fix(int a)
 {
 	return a+(a>>31&P);
 }
 struct num
 {
 	u32 x;
 	num(u32 a=0):x(a){}
	num operator+(num w)
	{
		return fix(x+w.x-P);
	}
	num operator*(num w)
	{
		return u64(x)*w.x%P;
	}
	void operator+=(num w)
	{
		x=fix(x+w.x-P);
	}
 };
 num s[5][1007],gs[11],iv[117],f0[57][1007],f1[57][1007],ans;
 void cal(int m,int n)
 {
 	int g=gcd(n,m);
 	num v=0;
 	for(int d=1;d<=g;++d)
 	if(g%d==0)
 	v+=f0[m/d][n/d]*phi(d);
 	v+=f1[m][n]*m;
 	ans+=v*iv[m*2];
 }
 int main()
 {
 	scanf("%d%d%u",&n,&m,&P);
 	if(m>n) m=n;
 	s[0][0]=iv[1]=1;
 	for(int i=2;i<=115;++i) iv[i]=iv[P%i]*(P-P/i);
 	for(int i=1;i<=n;++i)
 	{
 		f0[1][i]=f1[1][i]=s[0][i-1]+s[1][i-1]+s[2][i-1];
 		gs[1]=f0[1][i]+s[3][i-1];
 		for(int j=2;j<=3;++j) gs[j]=gs[j-1]*(gs[1]+(j-1))*iv[j];
 		for(int j=3;j;--j)
 		{
 			for(int k=n;k>=i;--k)
 			{
 				for(int t=1;t<=j;++t)
 				{
 					int w=k-t*i;
 					if(w>=0) s[j][k]+=gs[t]*s[j-t][w];
				 }
			 }
		 }
	 }
	 for(int i=2;i<=m;++i)
	 {
	 	for(int j=i;j<=n;++j)
	 	{
	 		for(int k=1;k<j;++k)
	 		f0[i][j]+=f0[i-1][j-k]*f0[1][k];
	 		if(i&1)
	 		{
	 			for(int k=2;k<j;k+=2)
	 			f1[i][j]+=f0[i>>1][k>>1]*f0[1][j-k];
			 }
			 else
			 {
			 	for(int k=1;k<j;++k) f1[i][j]+=f1[i-1][j-k]*f0[1][k];
			 	if(~j&1) f1[i][j]+=f0[i>>1][j>>1];
			 	f1[i][j]=f1[i][j]*iv[2];
			 }
		 }
	 }
	 for(int i=3;i<=m;++i) cal(i,n);
	 printf("%d\n",ans.x);
	 return 0;
 }

详情