网站会员系统源码,wordpress简约下载站模板下载,软件app开发制作多少钱,手机网页制作apphttps://www.luogu.org/problem/show?pid3200 首先#xff0c;我们不能保证要求的数的逆元和模域互质#xff1b; 所以我们要用分解质因数来抵消除法#xff1b; 其实逆元的话即使可行也会超时#xff1b; 那么我转载了#xff0c;实在没什么可以说的#xff1b; 另… https://www.luogu.org/problem/show?pid3200 首先我们不能保证要求的数的逆元和模域互质 所以我们要用分解质因数来抵消除法 其实逆元的话即使可行也会超时 那么我转载了实在没什么可以说的 另外卡特兰数 http://baike.baidu.com/link?urlSt3mmth0khr1jUoD9Vwdroupnfajo6hhTSgwvOkjAPrP0Htt12nZjsMue4T_5JhMopRqlhgAkCt2dDzd378Kg8xjsSYwGn3J_CMLgsvI4Psdhj3z0s4zTucxc1v6dRlP 话说这个方法好巧妙啊 http://blog.csdn.net/jiangshibiao/article/details/24009239 【转化】就是求卡特兰数。 【初始代码】 #includecstdio
using namespace std;
typedef long long ll;
ll prime[200005],a[200005];
bool f[2000005];
ll temp,n,p,i,j,cnt,mod;
ll pow(ll a,ll b)
{ ll ans; for (ans1;b;b1,aa*a%mod) if (b1) ansans*a%mod; return ans;
}
int main()
{ scanf(%lld%lld,n,mod); for (i2;in*2;i) { if (!f[i]) prime[cnt]i; for (j1;jcntprime[j]*in*2;j) f[prime[j]*i]true; } for (in2;in*2;i) for (j1,pi;jcntp;j) while (p%prime[j]0) a[j],p/prime[j]; for (i2;in;i) for (j1,pi;jcntp;j) while (p%prime[j]0) a[j]--,p/prime[j]; temp1; for (j1;jcnt;j) if (a[j]) temp(temp*pow(prime[j],a[j]))%mod; printf(%lld,temp);for (;;); return 0;
} 用欧拉筛法On的效率求出每个质数。然后枚举阶乘像质数表一样把一个数给分解。但是效率很低。 【优化1】如果一个数是合数我们可以把它的某个因子记下来。然后我们同样从开始枚举阶乘而且是倒着枚举。对于每个数如果它是合数我就把它分解。比如设f[n]为结果中含有n因子的个数。u是n的一个约数。那么我们可以f[u]f[n],f[n/u]f[n]。这样就不用多次用快速幂了。直到n是质数为止。 【优化2】开始可以把1–n的f[i]设为-1把n2–2*n(注意最后要除n1,所以从n2开始)的f[i]设为1.这样只需1次循环。 【AC代码】 #includecstdio
using namespace std;
typedef long long ll;
ll prime[200005],a[2000005],come[2000005];
ll temp,n,p,i,j,cnt,mod;
ll pow(ll a,ll b)
{ ll ans; for (ans1;b;bb/2,aa*a%mod) if (b1) ansans*a%mod; return ans;
}
int main()
{ scanf(%lld%lld,n,mod); for (i2;in*2;i) { if (!come[i]) prime[cnt]i; for (j1;jcntprime[j]*in*2;j) come[prime[j]*i]i; } temp1; for (i2;in;i) a[i]-1; for (in2;i2*n;i) a[i]1; for (in*2;i1;i--) if (come[i]) { a[come[i]]a[i]; a[i/come[i]]a[i]; } else temptemp*pow(i,a[i])%mod; printf(%lld,temp); return 0;
} 转载于:https://www.cnblogs.com/largecube233/p/6797912.html
