【问题描述】
小L有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为1~N(2<=N<=1015)。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻M(2<=M<=5,M<=N)个花圃中有不超过K(1<=K< M)个C形的花圃，其余花圃均为P形的花圃。
例如，N=10,M=5,K=3。则
CCPCPPPPCC 是一种不符合规则的花圃；
CCPPPPCPCP 是一种符合规则的花圃。
请帮小L求出符合规则的花园种数Mod 1000000007
由于请您编写一个程序解决此题。
【输入文件】
一行，三个数N,M,K。
【输出文件】
花园种数Mod 1000000007
【样例输入1】
10 5 3
【样例输出1】
458
【样例输入2】
6 2 1
【样例输出2】
18
【数据规模】
40%的数据中，N<=20；
60%的数据中，M=2；
80%的数据中，N<=105。
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u029
【题解】
先处理处1..m的情况,对于每个位置都有两个选择;
和0..(2^m)-1的二进制一一对应;
1的个数和1的个数对应;
处理出1的个数小于等于k的状态;
表示这些状态是可行的;
然后考虑整体往右移动一位;
然后获取了新的状态;
即
[l..r]
->[l+1..r+1]
这里枚举l..r的状态,然后对于新获取的状态;
只有两种情况;
r+1为0或者是r+1为1;
如果新获取的状态1的个数小于等于k;
则表示从l..r可以到达l+1..r+1;
这个可以用位运算搞出来;
(这个位运算自己推吧,看别人的程序挺可怕的..)
然后就能获取出一个二维的矩阵了;
求这个矩阵的(N-M)次幂;
然后枚举初始的M个位置的状态,和末尾的M个位置的状态;
看看练成环之后符不符合要求；
符合要求的话就递增答案.
这里矩阵乘法我写成函数的形式RE了。。。
所以就没写成函数啦
【完整代码】
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
const int INF = 0x3f3f3f3f;
const LL mod = 1000000007;
struct juzhen
{
LL a[64][64];
void init()
{
rep1(i,0,63)
rep1(j,0,63)
a[i][j] = 0;
}
};
int ma,num;
LL ans = 0,n,rr[100],m,k;
juzhen t,a;
bool bo[64+10];
void in()
{
cin >> n >> m >> k;
}
void pre()
{
ma = (1<<m)-1;
rep1(i,0,ma)
{
int j = i,cnt = 0;
while (j)
{
cnt+=(j&1);
j>>=1;
}
if (cnt>k)
bo[i] = false;
else
bo[i] = true;
}
t.init();
rep1(i,0,ma)
if (bo[i])
{
int te = ma-(1<<(m-1));
te = i&te;
te<<=1;
t.a[i][te] = 1;
if (bo[te+1])
t.a[i][te+1] = 1;
}
}
void special()
{
if (n==m)
{
int temp = 0;
rep1(i,0,ma)
if (bo[i])
temp++;
printf("%d
",temp);
exit(0);
}
}
void get_ksm()
{
LL tt = n-m;
a.init();
rep1(i,0,ma)
rep1(j,0,ma)
a.a[i][j] = t.a[i][j];
while (tt)
{
if (tt==1) break;
num++;
rr[num] = tt&1;
tt>>=1;
}
// exit(0);
rep2(i,num,1)
{
//a = cheng(a,a);
juzhen c;
c.init();
rep1(i,0,ma)
rep1(j,0,ma)
rep1(k,0,ma)
c.a[i][j] = (c.a[i][j] + a.a[i][k]*a.a[k][j])%mod;
rep1(i,0,ma)
rep1(j,0,ma)
a.a[i][j] = c.a[i][j];
if (rr[i]==1)
{
//a = cheng(a,t);
juzhen c;
c.init();
rep1(i,0,ma)
rep1(j,0,ma)
rep1(k,0,ma)
c.a[i][j] = (c.a[i][j] + a.a[i][k]*t.a[k][j])%mod;
rep1(i,0,ma)
rep1(j,0,ma)
a.a[i][j] = c.a[i][j];
}
}
}
void get_ans()
{
juzhen b;
rep1(i,0,ma)
if (bo[i])
{
b.init();
b.a[0][i] = 1;
//b = cheng(b,a);
juzhen c;
c.init();
rep1(i,0,ma)
rep1(j,0,ma)
rep1(k,0,ma)
c.a[i][j] = (c.a[i][j] + b.a[i][k]*a.a[k][j])%mod;
rep1(i,0,ma)
rep1(j,0,ma)
b.a[i][j] = c.a[i][j];
rep1(j,0,ma)
if (bo[j])
{
bool ok = true;
LL t = j<<m;
t = t|i;
rep1(k,1,m-1)
{
int d = (1<<m)-1;
d = d<<(m-k);
d = d&t;
d>>=(m-k);
if (!bo[d])
{
ok = false;
break;
}
}
if (ok)
ans = (ans+b.a[0][j])%mod;
}
}
}
void o()
{
cout << ans << endl;
}
int main()
{
//freopen("D:\rush.txt","r",stdin);
in();
pre();
special();
get_ksm();
get_ans();
o();
//printf("
%.2lf sec
", (double)clock() / CLOCKS_PER_SEC);
return 0;
}