【数学小考 4】 2015.07.13

  • sadness

巨胖的技能组合

[Description]

给定n个数,其中k个数有使用限制limit[i],求长度为m的不同排列(只是顺序不同算同一个排列)有多少个。

[Hint]

$n,m≤10^{5},k≤min(n,15),答案对 1000000007 取模$

[Solution]

容斥原理(自己脑补下就好了)。
其中组合数要求逆元。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int mod=1000000007;

int pow(ll a,int n){
ll ans=1;
while(n){
if(n&1) ans=ans*a%mod;
a=a*a%mod; n>>=1;
}
return ans;
}

int C(int n,int m){
if(n<0) return 0;
if(!m || n==m) return 1;
if(!n || n<m ) return 0;
if(m>n-m) m=n-m;
ll cn=1,cm=1;
for(int i=0;i<m;i++) cn=cn*(n-i)%mod,cm=cm*(m-i)%mod;
return cn*pow(cm,mod-2)%mod;
}

ll ans;
int n,m,k;

const int maxn=15;
int limit[maxn];
bool exceed[maxn];
void check(){
int x=m+n-1,cnt=0;
for(int i=0;i<k;i++)
if(exceed[i]){
cnt++;
x-=limit[i]+1;
}
ans=(ans+(cnt%2?-1:1)*C(x,n-1))%mod;
}
void search(int t){
for(int i=0;i<2;i++){
exceed[t]=i;
if(t==k-1) check();
else search(t+1);
}
}

int main(){
freopen("Dnf.in","r",stdin);
freopen("Dnf.out","w",stdout);
scanf("%d%d%d",&n,&k,&m);
for(int i=0;i<k;i++) scanf("%d",&limit[i]);
if(k) search(0);
else check();
printf("%lld",(ans+mod)%mod);
return 0;
}

巨胖的辗转相除

[Description]

给定n,找到所有a,b≤n的点对中辗转相除次数最多的数对(a,b)。

[Hint]

$n≤10^{12000}$

[Solution]

数据范围吓死人了-=|||
打表发现,这两个数就是斐波那契数列中仅小于n的两个数。

给出证明:
证明最优解是斐波那契数列相邻两项的方法:首先gcd(a,b)=1最优,因为gcd(a,b)>1我们可以把a,b同时整除gcd(a,b),辗转相除次数仍然相同,但是a,b更小。那么辗转相除的最终结果就是a1=0,b1=1。然后递归回去时,a,b的公式为:a2=b1=1,b2=a1+b1*k(k>0)那么当k=1时a2,b2最小,即a2=b1,b2=a1+b1,即斐波纳契数列,问题得证。
高精度实现就可以了

巨胖的最大约数

[Description]

给定n,求小于n的正整数中约数最多的数。

[Hint]

$n≤10^{9}$

[Solution]

满足条件的数有如下性质:越大大的质因数的指数越小。若不是这样,就一定可以调整到更优(想一想,为什么)。然后n只有这么大,最多用得到前面10个质因子,暴力枚举就好了。