T1.dnf
题意：给定 n 个技能，其中 k 个只能各使用 Li 次。求使用 m 次技能的次数组合有几种 (某种技能的使用次数不同，组合就不同)。(n,m<=100000,k<=15)
分析：注意到 k<=15, 这很有可能是容斥的题。
如果每种技能都可以使用无限次，根据插板法，所有的组合数为：
$$
C_{n+m-1}^{n-1}
$$
接着思考，如果有一种技能超过了 Li，现在将那 (Li+1) 次去掉，那么就相当于使用总数减少了 (Li+1) 次。接着就可以使用插板法求组合数：
$$
C_{n+m-1-(Li+1)}^{n-1}
$$
所以根据容斥原理：
$$
ans=\sum{\pm C_{n+m-1-\sum{(Li+1)}}^{n-1} }
$$
那么给出代码就是：
#include <iostream>
#include <cstring>
#include <cstdio>
#define MD 1000000007
#define MX 200050
using namespace std;
typedef long long ll;
ll frac[MX+1];
ll n,m,k,ans;
ll use[20];
void init()
{
frac[0]=1;
for(ll i=1;i<=MX;i++)frac[i]=frac[i-1]*i%MD;
}
inline ll ksm(ll x,ll t)
{
ll as=1;
while(t)
{
if(t&1)as=as*x%MD;
x=x*x%MD;
t>>=1;
}
return as;
}
inline ll inv(ll x){return ksm(x,MD-2);}
inline ll C(ll n,ll m){return frac[n]*inv(frac[m])%MD*inv(frac[n-m])%MD;}
void input()
{
scanf("%lld%lld%lld",&n,&k,&m);
for(ll i=1;i<=k;i++)scanf("%lld",&use[i]);
}
void sch(int pos,ll sgmt,ll num)
{
if(sgmt>m)return;
if(pos==k+1)
{
if(num%2==0)ans=(ans+C(n+m-1-sgmt,n-1))%MD;
else ans=(ans-C(n+m-1-sgmt,n-1)+MD)%MD;
return;
}
sch(pos+1,sgmt+use[pos]+1,num+1);
sch(pos+1,sgmt,num);
}
int main()
{
freopen("dnf.in","r",stdin);
freopen("dnf.out","w",stdout);
init();
input();
sch(1,0,0);
cout<<ans<<endl;
return 0;
}
T2.euclid
题意：给定一个 n，求 gcd(a,b) 递归层数最多的 a,b(a,b<=n) (n<=1e12000)
思路：考虑到 n 十分巨大，这道题一定会使用高精度。
分析之后不难发现，当 a,b 为相邻的两个斐波那契数时，递归层数最多。且 a<b 比 b<a 时更多一层。
由于斐波那契数相邻两项之比趋近于 1.618, 所以我们要计算到的斐波那契数大约需要 57700 项。
如果高精度加法速度较快，不压位可能可以通过，但是如果压 17 位通过把握更大。
有关卡常技巧：
1. 压位：
在 x64 系统内使用 long long 效率更高，带来的常数优化也更强，但是在 32 位系统，最好用 unsigned int 压 8 位。(亲测 17 位+O2 仅需 0.3 秒算完最大数据, 不压位 0.9 秒)
#define SIZ 1000000000000000000
2. 高精度模板：
为了获得更高的计算速度，我们的高精度加法函数最好写成 inline 的，且传入的参数都是指针，内部只有一个循环。这样效率更高。数组也应尽量开小一些。
typedef struct bigintger{ll x[669];}BI;
inline BI pls(BI *a,BI *b)//貌似传入指针，返回结构体是最快的
{
BI c;
int lens=max(a->x[0],b->x[0]);
c.x[lens+1]=0,c.x[1]=0;//这一行结合下一行可以避免 memset
for(register int i=1;i<=lens;i++)c.x[i]=(c.x[i]+a->x[i]+b->x[i])%SIZ,c.x[i+1]=(a->x[i]+b->x[i])/SIZ;//将进位和计算本位的循环合二为一
if(c.x[lens+1])++lens;
c.x[0]=lens;
return c;
}
3. 避免冗余操作：
在高精度加法之前，避免使用 memset 而是用一些特判代替。在计算斐波那契数时，最好只开 3 个变量轮流使用，并且通过指针访问那三个变量，交换变量时直接交换指针，速度回更快。
void work()
{
BI a,b,c;
BI *ap,*bp,*cp,*tmp;
ap=&a,bp=&b,cp=&c;
a.len=b.len=1;
a.x[1]=0,b.x[1]=1;
while(1)
{
*cp=pls(ap,bp);
if(big(cp,&n))
{
out(*ap);
puts("");
out(*bp);
puts("");
break;
}
tmp=ap;
ap=bp,bp=cp,cp=tmp;
}
}
4. 奸诈的技巧：
强制开 O2
#pragma GCC optimize(2)
所以总的代码就是这样的：
#include <iostream>
#include <cstring>
#include <cstdio>
#pragma GCC optimize(2)
#define len x[0]
#define SIZ 1000000000000000000
#define MX 14099
using namespace std;
typedef unsigned long long ll;
ll ten[19]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000};
typedef struct bigintger{ll x[669];}BI;
BI n;
inline BI pls(BI *a,BI *b)
{
BI c;
int lens=max(a->len,b->len);
c.x[lens+1]=0,c.x[1]=0;
for(register int i=1;i<=lens;i++)c.x[i]=(c.x[i]+a->x[i]+b->x[i])%SIZ,c.x[i+1]=(a->x[i]+b->x[i])/SIZ;
if(c.x[lens+1])++lens;
c.len=lens;
return c;
}
inline bool big(BI *a,BI *b)
{
if(a->len!=b->len)return a->len>b->len;
for(register int i=a->len;i>=1;--i)
if(a->x[i]!=b->x[i])
return a->x[i]>b->x[i];
return 0;
}
void out(BI a)
{
printf("%lld",a.x[a.len]);
for(register int i=a.len-1;i>=1;i--)printf("%018lld",a.x[i]);
}
void in(BI *a)
{
memset(a->x,0,sizeof(a->x));
a->len=0;
char ch[MX];
scanf("%s",ch);
int lens=strlen(ch);
for(register int i=0;i+i<lens;i++)swap(ch[i],ch[lens-i-1]);
for(register int i=0;i<lens;i++)a->x[i/18+1]=a->x[i/18+1]+(ch[i]-'0')*ten[i%18];
a->len=(lens-1)/18+1;
}
void work()
{
BI a,b,c;
BI *ap,*bp,*cp,*tmp;
ap=&a,bp=&b,cp=&c;
a.len=b.len=1;
a.x[1]=0,b.x[1]=1;
while(1)
{
*cp=pls(ap,bp);
if(big(cp,&n))
{
out(*ap);
puts("");
out(*bp);
puts("");
break;
}
tmp=ap;
ap=bp,bp=cp,cp=tmp;
}
}
int main()
{
freopen("euclid.in","r",stdin);
freopen("euclid.out","w",stdout);
in(&n);
work();
return 0;
}
T3.divisor
题意：求 1~N 中哪个数因子最多。(N<=1e9)
分析：又是一道打表题
怎么打表呢？
注意到这里是求因子个数，所以我们可以使用 O(NlnN) 的筛法求每个数的因子个数。问题是 1e9 的数组开不下，于是我们可以开一个 2e8 的数组，分 5 次筛，每次记录上一次的最多因子数。这样可以在 10 分钟内全部求出。
而且由于最多因子数是递增的，而且不会超过 sqrt(n) 个数，所以最终打出来的表还不到 1kb。
or#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int numbers[2000]=
{
1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,
7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,
166320,221760,277200,332640,498960,554400,665280,720720,1081080,
1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,
10810800,14414400,17297280,
21621600,
32432400,36756720,
43243200,
61261200,
73513440,
110270160,
122522400,
147026880,
183783600,
245044800,
294053760,
367567200,
551350800,
698377680,
735134400,
1000000001
};
int main()
{
freopen("divisor.in","r",stdin);
freopen("divisor.out","w",stdout);
int n;
cin>>n;
if(n==0)cout<<0<<endl;
else for(int i=0;i<=1500;i++)if(n>=numbers[i]&&n<numbers[i+1]){cout<<numbers[i]<<endl;return 0;}
}
0 条评论