注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2004(hnoi 2010) 公交路线  

2013-02-22 12:04:18|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
看到p<=10,我打赌这跟状压DP有关
看到n<=10^9,我打赌这跟矩乘有关

注意看这样一种路线
A B C _ _->_ B C A _->_ B _ A C
A B C _ _->A B _ _ C->_ B _ A C
虽然顺序不同,但是他们是同一种方案,都是A由1到4,C由3到5
所以我们不妨强制要求必须得最靠前的先走
这样一来就可以转移了
一个P位的二进制位,恰好有k个1且最高位为1表示状态
我刚开始不明白为什么恰好有K个也不明白为什么最高位为1,想到那个强制要求之后就懂了
所以合法状态最多有C(9,4)=126。
然后在构造矩阵,使用矩阵乘法,时间复杂度最高也只有log10^9*(126^3)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 15
#define MAXM 150
#define MOD 30031
#define get(n,k) ((n)>>(k-1)&1)
#define power(n)  (1<<(n))
#define lowbit(x) (x&(-x))
using namespace std;
struct Matrix
{
    int digit[MAXM][MAXM],n,m;
    friend Matrix operator * (const Matrix &a,const Matrix &b)
    {
        Matrix c;
        memset(c.digit,0,sizeof(c.digit));
        c.n=a.n,c.m=b.m;
        for(int i=1;i<=a.n;i++)
            for(int j=1;j<=b.m;j++)
                for(int k=1;k<=a.m;k++)
                    c.digit[i][j]=(c.digit[i][j]+a.digit[i][k]*b.digit[k][j])%MOD;
        return c;
    }
}p,ans;
int n,m,k,F[MAXN];
int v[MAXM],tot;
void DFS(int dep)
{
    if(dep>m)
    {
        int t=power(k-1);
        for(int i=2;i<=m;i++)
            t|=power(k-F[i]);
        v[++tot]=t;
        return ;
    }
    for(int i=F[dep-1]+1;i<=k;i++)
    {
        F[dep]=i;
        DFS(dep+1);
    }
}
void ptm()
{
    for(int i=1;i<=tot;i++)
        for(int j=1;j<=tot;j++)
        {
            int x=v[i]<<1^v[j]^power(k);
            if(x&&x==lowbit(x))  p.digit[i][j]=1;
        }
    p.n=p.m=tot,ans.n=1,ans.m=tot;
    ans.digit[1][1]=1;
}
Matrix Matrix_Power(int n)
{
    Matrix ans;
    memset(ans.digit,0,sizeof(ans.digit));
    ans.n=tot,ans.m=tot;
    for(int i=1;i<=tot;i++)
        ans.digit[i][i]=1;
    while(n)
    {
        if(n&1)  ans=ans*p;
        p=p*p,n>>=1;
    }
    return ans;
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    F[1]=1,DFS(2);
    ptm();
    p=Matrix_Power(n-m),ans=ans*p;
    printf("%d\n",ans.digit[1][1]);
    return 0;
}



  评论这张
 
阅读(857)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017