【数学小考 2】 2015.07.11

本来能打190的,第三题忘记取模,掉了100。

大胖的超级数字

[Description]

给定一个数x,求解它在多少种进制下的写法末位有且仅有k个0。

[Hint]

$n≤10^{15},k>n/500$

[Solution]

当x在B进制下末尾有k个0,当且仅当x能被$B^{k}$整除,又因为只有k个0,x又不能被$B^{k+1}$整除,现在我们要找出所有的B。
将x和B(假设确定)质因数分解
x=p1^a1*p2^a2*…*pn^an
B=p1^b1*p2^b2*…*pn^bn
设末尾至少有k个0的B有m个,有k+1个0的B有n个,所以ans=m-n,我们此时需要算出m,n。
求解m:根据条件,有bi*k≤ai≤bi*(k+1),所以0≤bi≤ai/k,所以bi的取值有0-ai/k,总方案数为$\prod(a_{i}+1)$$
同理求解n即可。
因为有$k>n/500$,大约素数只要筛到1000就好了。

大胖的神奇路径

[Description]

大胖从原点在数轴上左右移动共n次,其中要向左移动m次,求有多少种方案,使得大胖一直位于x的非负半轴。

[Hint]

多组数据(最多1000组),$0≤m≤n≤10^{6}$

[Solution]

转化一下模型,想象大胖在平面直角坐标系,从原点开始走,原题的向左走改成向右走,向右走改成向上走,最终走到(m,n-m),且轨迹不能越过y=x这条直线(时刻保持y≤x),这样就跟BZOJ一道题差不多了辣~
传送门>>http://www.lydsy.com/JudgeOnline/problem.php?id=3907
答案是C(n,m)-C(n+1,m)
注意当m< n/2时无解。

大胖的中国象棋

[Description]

在n*n的格子里放n个棋子,其中第i个棋子不能放在第i行或第i列,求有多少种方案,对m取模。

[Hint]

$n≤10^{17},m≤10^{6}$

[Solution]

打表找到规律切了==最后忘记模m爆0==
答案就是错排公式的平方==可以O(n)求解,但n比较大,怎么办呢,我们发现模p后f[n]每m个一循环,n直接模个m即可。
也可以递推求解,设g[n]=sqrt(f[n])
$ans=g[n]^{2}=g[n\%m]^{2}=(g[n\%m-1]+g[n\%m-2])*(i-1))^2$

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>

typedef long long ll;
const int maxn=1000001;
int f[maxn];

int main(){
ll n; int m;
scanf("%lld%d",&n,&m);
f[2]=1; n%=m;
for(int i=3;i<=n;i++) f[i]=(ll)(f[i-1]+f[i-2])*(i-1)%m;
printf("%lld",(ll)f[n]*f[n]%m);
return 0;
}