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

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]花园  

2015-08-07 23:19:56|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:dp,矩阵快速幂。

Link&Limit


        [洛谷1357]
        时间限制:1000ms  空间限制:131072kb

Description


        小L有一座环形花园,沿花园的顺时针方向,他把各个花圃编号为1~N。他的环形花园每天都会换一个新花样,但他的花园都不外乎一个规则,任意相邻M个花圃中有不超过K个C形的花圃,其余花圃均为P形的花圃。
        例如,N=10,M=5,K=3。则
        CCPCPPPPCC 是一种不符合规则的花圃;
        CCPPPPCPCP 是一种符合规则的花圃。
        请帮小L求出符合规则的花园种数Mod 1000000007

Input Format


        一行,三个数N,M,K。

Output Format


        花园种数Mod 1000000007.

Sample Input #1


10 5 3

Sample Output #1


458

Sample Input #2


6 2 1

Sample Output #2


18

Hint


        40%的数据中,N<=20;
        60%的数据中,M=2;
        80%的数据中,N<=10^5;
        100%的数据中,N<=10^15。

        据说是NOIP福建省夏令营的题目,这也太狠了...
        一道递推的题目,记f(i,s)为当前考虑到第i个花圃,(包括第i个花圃)前m个花圃状态为s的方案数(s是用一个二进制数表示状态,0为P形花圃,1为C形花圃)。状态间的转移还是比较明显的,就是去掉最后一个花圃,再在最开头加上一个花圃,而加上的花圃可能是0也可能是1,举几个例子。
        f(i,1011) = f(i-1,0110) + f(i-1,0111)
        f(i,0011) = f(i-1,0110) + f(i-1,0111)
        关于初值,由于花园是环形的,所以1~m号花圃会对n-m+2~n号花圃产生影响。为了确定产生的到底是什么样的影响,我们就需要枚举1~m号花圃的状态,对每种状态进行一次递推。设1~m号花圃的状态为s,则最终答案就是f(n+m,s).
        但是n ≤ 10^15有点太大了,就需要用矩阵快速幂加速递推。具体的操作可以参考下方的程序。

#include <cstdio>
#include <cstring>
#define MOD 1000000007
struct rect
{
int p,q;
long long x[35][35];
rect() { memset(x,0,sizeof(x));}
}ori,kk,t;
int m,r,lim;
long long n,ans = 0;
rect operator * (rect a,rect b)
{
int i,j,k;
long long tans;
rect c;
c.p = a.p; c.q = b.q;
for(i=0;i<a.p;i++) for(j=0;j<b.q;j++)
{
tans = 0;
for(k=0;k<a.q;k++) tans = (tans+a.x[i][k]*b.x[k][j])%MOD;
c.x[i][j] = tans;
}
return c;
}
rect power(rect a,long long b)
{
int i;
rect base = a,y;
y.p = y.q = lim;
for(i=0;i<lim;i++) y.x[i][i] = 1;
for(;b;b>>=1)
{
if(b&1) y = y*base;
base = base*base;
}
return y;
}
void build()
{
int i,x,cnt;
kk.p = kk.q = lim;
for(i=0;i<lim;i++)
{
x = i; cnt = 0;
for(;x;x>>=1) if(x&1) cnt++;
if(cnt>r) continue;
kk.x[i][i>>1] = 1; kk.x[i][(i>>1)|(1<<(m-1))] = 1;
}
}
int main()
{
int i,x,cnt;
scanf("%lld%d%d",&n,&m,&r); lim = 1<<m;
ori.p = 1; ori.q = lim;
build(); kk = power(kk,n);
for(i=0;i<lim;i++)
{
x = i; cnt = 0;
for(;x;x>>=1) if(x&1) cnt++;
if(cnt>r) continue;
ori.x[0][i] = 1;
t = ori*kk;
ans = (ans+t.x[0][i])%MOD;
ori.x[0][i] = 0;
}
printf("%lld",ans);
return 0;
}

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

历史上的今天

评论

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

页脚

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