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 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注