7
6
2015
1

bzoj 3120: Line

首先很容易想到DP,其次很容易想到是矩阵乘法,正常的玩法矩阵是 $$ q^n*P $$ 的,这个肯定玩不过去

然后就是想办法压抑下状态,首先我们知道我们关心的只是连续男生有A个的未知数两,所以可以改成n^q然后发现知道1和2的就可以知道3的所以可以存n^(q-1)然后发现不是所有的都可以比如说1个的有n个两个的有n个那肯定不可能出现所以状态就被压下去了

但是这道题这样依然很难在bzoj上通过,所以有一个矩阵乘法的小优化(虽然这个优化对一些矩阵会很慢,但是对于这样的转移矩阵来说就会快很多)

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <algorithm>
#include <cerrno>
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int mod = 1000000007;
const int Size = 200;
struct Matrix{
	int n;
	int x[Size][Size];
	Matrix(){ memset(x,0,sizeof(x)); }
	int *operator[](int A){ return x[A]; } 
}C,ret,A,B;
inline void mul(Matrix &A,Matrix &B,Matrix &ans){
	ans.n=A.n;
	memset(C.x,0,sizeof(C.x));
	for (int k=0;k<A.n;k++)
		for (int i=0;i<A.n;i++)
			if (A[i][k])
				for (int j=0;j<A.n;j++)
					if (B[k][j]) C[i][j]=(C[i][j]+(LL)A[i][k]*B[k][j])%mod;
	for (int i=0;i<A.n;i++)
		for (int j=0;j<A.n;j++) ans[i][j]=C[i][j];
}
inline void power(Matrix &A,LL B){
	memset(ret.x,0,sizeof(ret.x)); ret.n=A.n;
	for (int i=1;i<A.n;i++)
		ret[i][i]=1;
	while (B){
		if (B&1) mul(ret,A,ret);
		mul(A,A,A);
		B>>=1;
	}
}
pair<int,int>List[100];
int tot;
int n,q,p,c[11][11];
LL m;
inline void addtrans(Matrix &A,int j1,int a1,int a2,int j2,int b1,int b2,int num){
	if (j2>q) return;
//	printf("addtrans(%d,%d,%d,%d,%d,%d) %d\n",j1,a1,a2,j2,b1,b2,num);
	int pos1=lower_bound(List+1,List+tot+1,make_pair(a1,a2))-List;
	int pos2=lower_bound(List+1,List+tot+1,make_pair(b1,b2))-List;
	A[pos1*(q+1)+j1][pos2*(q+1)+j2]+=num;
}
inline void addtrans(Matrix &A,int j1,int a,int j2,int b,int num){
	if (j2>q) return;
	A[a*(q+1)+j1][b*(q+1)+j2]+=num;
}
inline void work2(){
	for (int i=0;i<=n;i++)
		for (int j=0;j+i<=n;j++)
			List[++tot]=make_pair(i,j);
	A.n=B.n=tot*(q+1)+q+1;
	for (int j=0;j<=q;j++)
		for (int a1=0;a1<=n;a1++)
			for (int a2=0;a1+a2<=n;a2++)
				for (int k1=0;k1<=a1;k1++)
					for (int k2=0;k2<=a2;k2++)
						addtrans(A,j,a1,a2,j+(k1+k2==n),n-k1-k2,k1,c[a1][k1]*c[a2][k2]);
	power(A,m);
	int p=lower_bound(List+1,List+tot+1,make_pair(n,0))-List;
	B[0][p*(q+1)]=1;
	mul(B,ret,B);
	int ans=0;
	for (int i=0;i<B.n;i++) ans=(ans+B[0][i])%mod;
	printf("%d\n",ans);
}
	
inline void work1()
{
	A.n=B.n=n*(q+1)+(q+1);
	for (int j=0;j<=q;j++)
		for (int i=0;i<=n;i++)
			for (int k=0;k<=i;k++)
				addtrans(A,j,i,j+(k==n),n-k,c[i][k]);
	power(A,m);
	B[0][n*(q+1)]=1;
	mul(B,ret,B);
	int ans=0;
	for (int i=0;i<B.n;i++) ans=(ans+B[0][i])%mod; 
	printf("%d\n",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("line.in","r",stdin);
	freopen("line.out","w",stdout);
#endif
	n=read(); scanf("%lld",&m),p=read(),q=read();
	c[0][0]=1;
	for (int i=1;i<=n;i++){
		c[i][0]=1;
		for (int j=1;j<=i;j++)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	if (p==0){ printf("0\n"); return 0; }
	if (p==1){ printf("1\n"); return 0; }
	if (p==2){ work1(); return 0; }
	work2(); return 0;
}

 

Category: 未分类 | Tags: | Read Count: 1160
Avatar_small
Ebony Butlin 说:
2019年4月02日 14:44

All the lines have been disconnected from the terms and for the new replacement of the lines actually be figure out. Vincent for the time machine now for the professional assignment writers having actually working for the vector to including well.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com