「BZOJ2004」[HNOI2010] Bus 公交线路

2015年1月31日4,6870

Description

小Z所在的城市有N个公交车站，排列在一条长(N-1)km的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1km。作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路： 1．设共K辆公交车，则1到K号站作为始发站，N-K+1到N号台作为终点站。 2．每个车站必须被一辆且仅一辆公交车经过（始发站和终点站也算被经过）。 3．公交车只能从编号较小的站台驶往编号较大的站台。 4．一辆公交车经过的相邻两个站台间距离不得超过Pkm。在最终设计线路之前，小Z想知道有多少种满足要求的方案。由于答案可能很大，你只需求出答案对30031取模的结果。

Input

仅一行包含三个正整数N K P，分别表示公交车站数，公交车数，相邻站台的距离限制。

Output

仅包含一个整数，表示满足要求的方案数对30031取模的结果。

Sample Input

样例一：10 3 3
样例二：5 2 3
样例三：10 2 4

Sample Output

1
3
81

HINT

「样例说明」
样例一的可行方案如下：
(1,4,7,10)，(2,5,8)，(3,6,9)
样例二的可行方案如下：
(1,3,5)，(2,4)
(1,3,4)，(2,5)
(1,4)，(2,3,5)
「数据规模」
40% N<=1000
100% 1<n<109，1<p<=10，k<n，1<k<=p

题解

参见ydc博客

http://ydcydcy1.blog.163.com/blog/static/21608904020131220135392/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define mod 30031
#define inf 1000000000
#define rad 100000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int bin[20];
int n,K,P,cnt;
int v[205];
struct M{
	ll v[205][205];
	M(){
		memset(v,0,sizeof(v));
	}
	friend M operator*(M a,M b){
		M c;
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=cnt;j++)
			{
				for(int k=1;k<=cnt;k++)
					c.v[i][j]+=a.v[i][k]*b.v[k][j];
				c.v[i][j]%=mod;
			}
		return c;
	}
	friend M operator^(M a,int b){
		M ans;
		for(int i=1;i<=cnt;i++)ans.v[i][i]=1;
		for(int i=b;i;i>>=1,a=a*a)
			if(i&1)ans=ans*a;
		return ans;
	}
}a,b,ans;
int lowbit(int x)
{
	return x&(-x);
}
void dfs(int now,int num,int sta)
{
	if(num==K)
	{
		v[++cnt]=sta;
		return;
	}
	for(int i=now-1;i;i--)
		dfs(i,num+1,sta+bin[i-1]);
}
void pre()
{
	for(int i=1;i<=cnt;i++)
		for(int j=1;j<=cnt;j++)
		{
			int x=(v[i]<<1)^bin[P]^v[j];
			if(x==lowbit(x))
			    b.v[i][j]=1;
		}
}
int main()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	n=read();K=read();P=read();
	dfs(P,1,bin[P-1]);
	pre();
	ans.v[1][1]=1;
	M t=b^(n-K);
	ans=ans*t;
	printf("%d\n",ans.v[1][1]);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define mod 30031

#define inf 1000000000

#define rad 100000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int bin[20];

int n,K,P,cnt;

int v[205];

struct M{

ll v[205][205];

M(){

memset(v,0,sizeof(v));

}

friend M operator*(M a,M b){

M c;

for(int i=1;i<=cnt;i++)

for(int j=1;j<=cnt;j++)

{

for(int k=1;k<=cnt;k++)

c.v[i][j]+=a.v[i][k]*b.v[k][j];

c.v[i][j]%=mod;

}

return c;

}

friend M operator^(M a,int b){

M ans;

for(int i=1;i<=cnt;i++)ans.v[i][i]=1;

for(int i=b;i;i>>=1,a=a*a)

if(i&1)ans=ans*a;

return ans;

}

}a,b,ans;

int lowbit(int x)

{

return x&(-x);

}

void dfs(int now,int num,int sta)

{

if(num==K)

{

v[++cnt]=sta;

return;

}

for(int i=now-1;i;i--)

dfs(i,num+1,sta+bin[i-1]);

}

void pre()

{

for(int i=1;i<=cnt;i++)

for(int j=1;j<=cnt;j++)

{

int x=(v[i]<<1)^bin[P]^v[j];

if(x==lowbit(x))

b.v[i][j]=1;

}

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

n=read();K=read();P=read();

dfs(P,1,bin[P-1]);

pre();

ans.v[1][1]=1;

M t=b^(n-K);

ans=ans*t;

printf("%d\n",ans.v[1][1]);

return 0;

}

« 「BZOJ2073」[POI2004] PRZ 「fjWC2015」三视图 »

hzwer.com _ Home | http://hzwer.com

「BZOJ2004」[HNOI2010] Bus 公交线路

Description

Input

Output

Sample Input

Sample Output

HINT

分类目录

热门文章

Myfriends

近期评论