省选模拟十

2016.02.19 16:38 Fri | 79次阅读 | 旧日oi | 固定链接 | 源码

T1 图计数

题目大意

给出n,m求m的(n的整数划分个数)次幂,取模999999599。
n,m<=200000。

题解

第二部分直接快速幂,但是要注意由于方案数在指数上,所以第一步求方案数的过程要取模mod-1。
第一部分怎么求呢?
如果$O(n^2)$可以接受,那么有两种办法。
1.直接完全背包。令f[i][j]表示用1到i划分j的方案数,则f[i][j]=f[i-1][j]+f[i][j-i]。
2.令f[i][j]表示用i个数划分j的方案,对于一种方案,考虑其中最小的数,如果是1,那么f[i][j]=f[i-1][j-1],否则f[i][j]=f[i-j][j],相当于把所有数减去1.
注意这两种状态中i表示的意义不同。
这两种方法各有优劣,但是如果我们把两种算法组合一下就完美了。
对于n的划分,小于$sqrt(n)$的数可以用完全背包搞。
而大于根号n的数一定不超过$sqrt(n)$个,所以恰好可以用第二种方法。
每种的时间复杂度都是$O(nsqrt(n))$

我的程序

#include <bits/stdc++.h>
using namespace std;
char getc()
{   
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read()
{
    static char ch;static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return D;
}
#define mod 999999599
#define ll long long
#define N 200005
int f[N],g[2][N],ans,D;
int n,m;
ll qpow(ll x,ll k,ll p)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=ret*x%p;
        k>>=1;x=x*x%p;
    }
    return ret;
}
int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    cin>>n>>m;
    f[0]=1;
    int k=min(n,450);
    for(int i=1;i<=k;i++) 
    for(int j=i;j<=n;j++) 
        f[j]=(f[j]+f[j-i])%(mod-1);
    if(k==n)
    {
        printf("%lld\n",qpow(m,f[n],mod));
        return 0;
    }
    ans=f[n];g[D][0]=1;
    for(int j=1;j<=n/k;j++)
    {
        D^=1;memset(g[D],0,sizeof(g[D]));
        for(int i=451;i<=n;i++)
            g[D][i]=(g[D^1][i-451]+g[D][i-j])%(mod-1);
        for(int i=0;i<=n;i++) 
            ans=(ans+1ll*f[i]*g[D][n-i]%(mod-1))%(mod-1);
    }
    printf("%lld\n",qpow(m,ans,mod));
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T2 装饰

题目大意

题解

每一列只会有六种情况rg,gr,rb,br,gb,bg
每种情况后面只会出现两种情况,比如rg后面只能接gb,br。而这种转移实际上形成了两个三元环。两种状态没有交集。
以rg,gb,br为例,我们可以求出每种情况出现多少次:rg:G+R-m,gb;m-G:br:m-R
然后问题变成了一个012构成的长度为m的串,0出现多少次,1出现多少次,2出现多少次,相邻数字不同的方案数。
这个东西怎么求?
我们考虑0的位置,相邻两个0之间一定是121212或212121,如果间隔为偶数,那么12个数相同,否则差1,那么我们令t=abs(R-G)(就是gb和br的数量差)。那么我们至少需要t个长度为奇数的间隔,或者是t+2个,t+4个。
设0的个数为a,那么这a个数可能形成a-1个间隔,a个间隔,a+1个间隔,再枚举长度为奇数的间隔的个数,用组合数求解方案数。
具体的实现可以参考代码,不懂可以联系QQ973289085。

我的程序

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 2000005
int m,r,g,b,a,c,t;
ll p[N],_inv[N],inv[N],ans;
ll qpow(ll x,ll k)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=ret*x%mod;
        k>>=1;x=x*x%mod;
    }
    return ret;
}
ll C(int n,int m)
{
    if(m>n||n<0||m<0) return 0;
    return p[n]*inv[m]%mod*inv[n-m]%mod;
}
void work1()
{
    for(int i=t;i<=a-1;i+=2)
    {
        ll k=C(a-1,i)*C((m-(a-1)*2-1-(a-1-i))/2+a-2,a-2)%mod;
        ans=(ans+k*qpow(2,a-1-i)%mod*C(i,(i-t)/2)%mod)%mod;
    }
}
void work2()
{
    for(int i=t;i<=a;i+=2)
    {
        ll k=C(a,i)*C((m-a*2-(a-i))/2+a-1,a-1)%mod;
        ans=(ans+k*qpow(2,a-i)%mod*C(i,(i-t)/2)%mod*2)%mod;
    }
}
void work3()
{
    m++;a++;
    for(int i=t;i<=a;i+=2)
    {
        ll k=C(a,i);
        k=k*C((m-a*2-(a-i))/2+a-1,a-1)%mod;
        ans=(ans+k*qpow(2,a-i)%mod*C(i,(i-t)/2)%mod)%mod;
    }
}
int main()
{
    freopen("decoration.in","r",stdin);
    freopen("decoration.out","w",stdout);
    cin>>m>>r>>g>>b;
    if(r>m||g>m||b>m)
    {
        puts("0");
        return 0;
    }
    p[0]=p[1]=_inv[0]=_inv[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=2000000;i++) 
    {
        p[i]=p[i-1]*i%mod;
        _inv[i]=(mod-mod/i)*_inv[mod%i]%mod;
        inv[i]=inv[i-1]*_inv[i]%mod;
    }
    a=r+g-m,b=m-g,c=m-r;
    if(b<c) swap(b,c);
    t=b-c;
    if(t>a+1)
    {
        puts("0");
        return 0;
    }
    if(a>1) work1();
    if(a>0) work2();
    work3();
    printf("%lld\n",ans*2%mod);
}

T3 幂

题目大意

给出a,b,求x∈[1,a],y∈[1,b],$x^y$的取值个数。$a,b<=10^9$

题解

首先不考虑1……
我们先找出所有不能被表示成$a^b$(b>1)的数。
怎么找?先找能被表示出来的。只需要暴力枚举2到$sqrt(n)$再枚举次数就可以了。
对于不能被表示出来的,它们的1....b次方肯定都互不相同。
对于一个不能被表示出的数,设为c,令x为使得$c^x<=a$的最大的x,我们发现,如果两个c对应的x相同,那么这两个c对答案的贡献是一样的!
而x最大是29,所以我们可以统计出x=1...29时的c的个数,然后问题变成了求
对于每一个x,求出$(c^a)^p),1<=a<=x,1<=p<=b)$的个数,也就ap的取值有多少。
这个怎么求?
把[1,xb]分成x段,每段长为b,如果第i段中的t能被某个xy表示,那么t一定能被[i,x]中的某个数整除。
这部分可以用容斥原理解决。然而x可以到29,但是如果有一个数是另一个数的倍数的话,这个数就没用了,经过剪枝最多有15个左右。
最后答案不要忘了+1
最终复杂度$O(2^{15}*15*30+sqrt(a)log(sqrt(a))$

我的程序

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a,b;
set<int> s;
int num[30],p[100005];
ll ans;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll work(ll l,ll r,int a,int b)
{
    static int st[20],top;
    static ll ret;
    ret=0;top=0;
    for(int i=a;i<=b;i++)
    {
        bool flag=1;
        for(int j=a;j<i;j++)
        if(i%j==0) {flag=0;break;}
        if(flag) st[top++]=i;
    }
    for(int i=1;i<(1<<top);i++)
    {
        bool flag=0;ll tmp=1;
        for(int j=0;j<top;j++)
        if(i>>j&1) 
        {
            flag^=1;
            if(tmp==1) tmp=st[j];
            else tmp=tmp*st[j]/gcd(tmp,st[j]);
        }
        tmp=r/tmp-(l-1)/tmp;
        ret+=(flag?tmp:-tmp);
    }
    return ret;
}
int main()
{
    freopen("power.in","r",stdin);
    freopen("power.out","w",stdout);
    cin>>a>>b;
    int last=2;
    for(;last*last<=a;last++) 
    {
        ll ret=last;
        for(int j=2;;j++) 
        {
            ret*=last;
            if(ret>a) {p[last]=j-1;break;}
            s.insert(ret);
        }
        if(s.insert(last).second) num[p[last]]++;
    }
    while(*s.begin()<last) s.erase(s.begin());
    num[1]=(a-last+1)-s.size();
    for(int k=1;k<30;k++)
    {
        for(int i=1;i<=k;i++)
        ans=(ans+num[k]*work(1ll*(i-1)*b+1,1ll*i*b,i,k));
    }
    printf("%lld\n",ans+1);
}
  • dashgua 2016-02-26 17:22:18

    最好换一下 mathjax 的渲染器。。。我就用 SVG 的渲染器。。。

  • dashgua 2016-02-26 17:23:34

    然而 hexo 并不知道怎么设置。。。