T1 巨胖的技能组合

题目:

考试最后做这道题的。
当时就听得boshi大喊一声:容斥!然后他就Ak了
然而我还是不会做
最后写了个50分的dp却得了70分。。。

正解:容斥+组合数
先假设所有的技能都能用无限次,根据插板法(考试时我还不会。。。)可以得到这样的情况方案数是:
$$C_{n+m-1}^{n-1}$$

然后我们来排除某些技能使用超限的情况

首先任选1个技能,故意让它超限(首先这个技能必须是有限制的技能),及使它的使用次数为Li+1次(因为这样剩余的总技能使用次数更大),再假设别的技能都能无限使用,看剩下的总技能使用次数和剩下的技能能组成多少种方案,这样拿原来假设每个技能都能无限使用时得到的值减去这个值就行了

但是我们会发现我们多减了,比如两个技能同时超限的情况就被多减了,于是我们和上面一样,任选一个技能,故意让它们超限,算出方案数,加到答案中。但我们又多加了三个技能同时超限的情况,所以减去。。。

以此类推,说白了就是容斥,选偶数个技能时加到答案,选奇数个时减去

这里要用到组合数,预处理一下阶乘和它们的逆元就行了

代码:

#include <bits/stdc++.h>
#define MOD (1000000007)
using namespace std;
typedef long long LL;
LL n,k,m,t[20],f[20][100005],ans,po[200005],ni[200005];
LL C(LL a,LL b){return po[a]*ni[b]%MOD*ni[a-b]%MOD;}
void dfs(LL cnt,LL fl,LL tot)
{
    if(tot<0)return;
    if(cnt==k+1)
    {
        ans=(ans+fl*C(tot+n-1,tot)%MOD+MOD)%MOD;
        return;
    }
    dfs(cnt+1,fl,tot),dfs(cnt+1,-fl,tot-t[cnt]-1);
}
LL qpow(LL a,LL b)
{
    LL sum=1;
    while(b)
    {
        if(b&1)sum=sum*a%MOD;
        b>>=1,a=a*a%MOD;
    }
    return sum;
}
int main()
{
    freopen("dnf.in","r",stdin),freopen("dnf.out","w",stdout);
    scanf("%lld%lld%lld",&n,&k,&m),memset(f,-1,sizeof(f)),po[1]=1,ni[1]=1;
    for(int i=2;i<n+m;i++)po[i]=po[i-1]*i%MOD;
    ni[n+m-1]=qpow(po[n+m-1],MOD-2);
    for(int i=n+m-2;i>=2;i--)ni[i]=(i+1)*ni[i+1]%MOD;
    for(int i=1;i<=k;i++)scanf("%lld",&t[i]);
    dfs(1,1,m),printf("%lld\n",ans);
    return 0;
}

T2 巨胖的辗转相除

题目:

我一看。。。辗转相除计算次数最多的不就是斐波那契数列相邻两项么?因为它们gcd一次其实就是向前移动一位
打标证明了一下
然后高精度压位(我压了8位)
首先打了个递推的加法,发现最大数据5s。。。
然后我就打了个二分+logn计算斐波那契数列,复杂度理论上是log2级别的(不带高进度复杂度),然而我写的高精度乘法常数巨大,最大数据10s。。。
于是我开始疯狂优化加法,去除了没必要的memset,然后用unsigned char自动溢出滚动数组(防止swap),最后加法省去了一个swap就0.9s过最大数据
怕出事,写了个读入优化,0.6s过了

代码:

#include <bits/stdc++.h>
#define MOD (100000000)
using namespace std;
typedef unsigned char UC;
struct BI
{
    int arr[2000],cnt;
    BI(){cnt=0;}
    void check()
    {
        int d=0;
        for(int i=0;i<cnt;i++)arr[i]+=d,d=arr[i]/MOD,arr[i]%=MOD;
        while(d)arr[cnt]=d,d=arr[cnt]/MOD,arr[cnt]%=MOD,cnt++;
    }
    void operator = (int a){memset(arr,0,sizeof(arr)),arr[0]=a,cnt=1,check();}
    void work(BI a,BI b)
    {
        cnt=a.cnt;
        for(int i=0;i<cnt;i++)arr[i]=a.arr[i];
        for(int i=0;i<b.cnt;i++)arr[i]+=b.arr[i];
        check();
    }
    bool operator <= (BI a)
    {
        if(cnt==a.cnt)
        {
            for(int i=cnt-1;i>=0;i--)
            {
                if(arr[i]<a.arr[i])return 1;
                if(arr[i]>a.arr[i])return 0;
            }
            return 1;
        }
        if(cnt<a.cnt)return 1;
        return 0;
    }
    void print()
    {
        printf("%d",arr[cnt-1]);
        for(int i=cnt-2;i>=0;i--)printf("%.8d",arr[i]);
        putchar('\n');
    }
}fib[300],n;
char str[20000];
int strl;
int main()
{
    freopen("euclid.in","r",stdin),freopen("euclid.out","w",stdout);
    char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))str[strl++]=c,c=getchar();
    for(int i=strl-1;i>=0;i-=8)
    {
        int k=0;
        for(int j=i,l=1;j>i-8&&str[j];j--,l*=10)k=k+l*(str[j]-'0');
        n.arr[n.cnt++]=k;
    }
    fib[0]=1,fib[1]=1,fib[2]=2;UC cur=2,pre=1,post=0;
    while(fib[cur]<=n){cur++,pre++,post++,fib[cur].work(fib[pre],fib[post]);}
    fib[post].print(),fib[pre].print();
    return 0;
}

T3 巨胖的最大约数

题目:

个人感觉做法很玄学。。。
评测发现程序访问了左闭右开的素数表的右端。。。然后0分re,痛彻心扉地删掉了一个等于号以后过了
首先没必要从1~n筛素数,因为其实大素数根本不用考虑(比如一个很大的素数它的约数个数为1,而且大素数相乘得到的数字虽然大,但是约数少啊),算了算发现搞出1~100的素数就行了(应该还不用到100,它们乘起来已经很大了)
推了一下约数个数公式:设它分解质因数以后质因数的次数分别问a1,a2,a3…那它的约数个数就是(a1+1)×(a2+1)×(a3+1)…
于是打了个很玄学的搜索,用上面那些素数组合到一起(乘法),记录约数个数和大小,最后求得答案
居然还真AC了。。。真玄学
(也许能证但不是很想(lande)证)
代码:

#include <bits/stdc++.h>
#define PS (25)
using namespace std;
typedef long long LL;
static const LL p[PS]=
{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
LL n,mx,ans;
void dfs(LL cur,LL cnt,LL tot)
{
    if(cnt>=PS)
    {
        if(tot>mx||(tot==mx&&cur<ans))ans=cur,mx=tot;
        return;
    }
    dfs(cur,cnt+1,tot);
    for(LL i=p[cnt],j=2;cur*i<=n&&(cur*i)%i==0&&cur*i>0;i*=p[cnt],j++)
        dfs(cur*i,cnt+1,tot*j);
}
int main()
{
    freopen("divisor.in","r",stdin),freopen("divisor.out","w",stdout);
    scanf("%lld",&n),dfs(1,0,1),printf("%lld\n",ans);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *