清北省选模拟赛 T1 积水 ——组合数+高精度
组合数 高精度   发布于 2017-01-23   281人围观  0条评论
组合数 高精度   发表于 2017-01-23   281人围观  0条评论

                                            积水

问题描述

       清北学堂某幢楼的屋顶上要安装一根横梁,其横截面是一个有N个顶点的直角多边形,也就是说,多边形是每个内角不是90°就是270°,将多边形放入直角坐标系中,它的每条边都与坐标轴平行。为了减轻承重,横梁不能出现在下雨天积水的情况,而且由于施工队不靠谱,横梁的安放角度是不确定的,所以需要保证横梁在被转了0°、90°、180°和270°时都不会积水。例如,图1和图2 的横截面都表示了一根合法的横梁,但图3和图4就显然不合法了。

          图1                          图2                       图3                           图4


       现在,给出直角多边形的顶点数N,求有多少个长度为N的01序列对应了某种合法的横梁横截面。

输入格式

       一行1个整数N。

输出格式

       一行1个整数,表示满足要求的01序列数量。

样例输入

6

样例输出

6

数据范围

对于10%的数据,n<=15;

对于30%的数据,n<=50000;

对于50%的数据,n<=106

对于100%的数据,n<=1010000

题解

省选模拟赛完挂,感觉自己吃枣药丸。。。

这是我省选模拟唯一做出来的题(做了3个小时,高精度调了老长时间,感觉自己码力巨弱,连普及组的选手都快不如了)……

不多说,看这道题的性质。

数据是1010000啊,所以这道题一定有什么性质……

我们枚举序列,注意到如果有两个以上的0连续出现(哪怕是一个在开头一个在结尾),这样的序列一定是不合法的,这是第一条性质。

第二个注意到,90度的角(个数记为x)和270的角(个数记为y)对整个多边形的贡献(总角度)一定满足多边形内角和公式180°(n-2),化简后即x+3y=2(n-2);并且x+y=n。所以我们在这里得到了什么?一个二元一次方程组!也就是说,对于某个确定的n,其多边形中的x和y一定是唯一确定的。

这两条性质对我们解这道题产生了极大的帮助。

然后我们开始列限制条件:

            1.首先根据第二个性质,我们知道,x=n/2+2,y=n/2-2,x-y=4.

            2.根据第二个性质,我们很容易得到,考虑合法的方案而不是不合法的方案才是最佳的选择。考虑合法的方案的话就非常OK了。

所以说结论是什么呢?

ans = C(x+1,x-4) + C(x-1,x-6)(当然这是初始结论,容易TLE,至于高端结论,请自行展开化简……)

然后我们考虑高精压位暴力求解组合数。我的代码是5位一压(不开O2TLE三个点),实际上开longlong的话8位一压就行了。

为什么要压位呢?压位可以降低时间复杂度。

优化时间复杂度的话,还是继续推结论的好,不然暴力要做10遍高精乘高精,O(nm)的

还有一种方法,可以用FFT,做到nlogn的复杂度(然而我并不会……)

数据:http://pan.baidu.com/s/1qY8k7mc 数据seeper

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10005;
int n;
long long ans = 1,ans1 = 1;
long long a[maxn<<3];
long long b[maxn<<3];
char nk[maxn];
long long cnt = 0,sum = 0;
long long k[maxn];
long long x1[maxn];
long long y2[maxn];
long long kq[maxn<<3];
long long yt[maxn];
int lena,lenb,kp,lenx1,leny2,lenyt;
int gjdiv(long long x[],int lenx,long long y[],long long u){//高精除单精 
	int l = lenx;
	for(int i = l - 1;i >= 0;i--){
		y[i] = x[i];
	}
	long long tmp = 0;
	for(int i = l - 1;i >= 1;i--){
		tmp = y[i] % u * 100000;
		y[i-1] += tmp;
		y[i] = y[i] / u;
	}
	y[0] = y[0] / u;
	while(y[l-1] == 0)l--;
	return l;
}
int gjj1(long long x[],int lenx,long long y[],long long u){//高精加减单精 
	int leny = lenx;
	y[0] = x[0] + u;
	if(y[0] >= 100000)y[1] += 1,y[0] %= 100000;
	if(y[0] < 0)y[1] -= 1,y[0] += 100000;
	for(int i = 1;i < leny;++i){
		y[i] += x1[i];
		if(y[i] >= 100000)y[i+1] += 1,y[i] %= 100000;
		if(y[i] < 0)y[i+1] -= 1,y[i] += 100000;
	}
	if(y[leny])leny++;
	while(!y[leny] && !y[leny-1])leny--;
	return leny;
}
int gjmul(int lenx,long long x[],int leny,long long y[],long long c[]){//高精乘高精 
	int lenc = lenx;
	for(int i = 0;i < lenc;++i)c[i] = 0;
	for(int i = 0;i < leny;++i)
		for(int j = 0;j < lenx;++j){
			c[i+j] += x[j] * y[i];
			if(c[i+j] >= 100000){
				c[i+j+1] += (c[i+j] / 100000);
				c[i+j] %= 100000;
			}
		}
	lenc = lenx + leny + 20;
	while(c[lenc - 1] == 0)
		lenc--;
	return lenc;
}
int gjj(int lenx,long long x[],int leny,long long y[],long long c[]){//高精加高精 
	int lenc = lenx;
	for(int i = 0;i < lenc;i++)c[i] = x[i];
	for(int i = 0;i < lenx;i++){
		c[i] = c[i] - y[i];
		if(c[i] < 0){
			c[i] += 100000;
			c[i+1] -= 1;
		}
	}
	if(c[lenc-1])return lenc;
	else{
		while(c[lenc-1] == 0)
			lenc -= 1;
		return lenc;
	}
}
int pkl[7] = {0,1,10,100,1000,10000,100000};
int main(){
	freopen("seeper.in","r",stdin);
	freopen("seeper.out","w",stdout);
	scanf("%s",nk);
	int len = strlen(nk);
	for(int i = len - 1;i >= 0;i--){
		cnt++;
		sum = sum + (nk[i] - '0') * pkl[cnt];
		if(cnt == 6){
			k[kp++] = sum % 100000;
			sum /= 100000;
			cnt = 1;
		}
	}
	k[kp++] = sum;
	sum = 0;
	cnt = 0;
	if(kp == 1 && k[0] <= 15){
		if(k[0] % 2 == 1 || k[0] < 4){
			printf("0\n");
			return 0;
		}
		if(k[0] == 4){
			printf("1\n");
			return 0;
		}
		int x = (k[0] + 4) >> 1;
		int y = (k[0] - 4) >> 1;
		for(int i = max(y,x+1-y) + 1;i <= x+1;++i){
			ans = ans * i;
		}
		for(int i = 2;i <= min(y,x+1-y);++i){
			ans /= i;
		}
		for(int i = max(y-2,x-y+1) + 1;i <= x-1;++i){
			ans1 *= i;
		}
		for(int i = 2;i <= min(y-2,x-y+1);++i){
			ans1 /= i;
		}
		if(n == 6)ans1 = 0;
		printf("%lld\n",ans-ans1);
	}
	else{
		if(k[0] % 2 == 1){
			printf("0\n");
			return 0;
		} 
		lenx1 = gjdiv(k,kp,x1,2ll);
		lenx1 = gjj1(x1,lenx1,kq,2ll);
		for(int i = 0;i < lenx1;i++){
			x1[i] = kq[i];
		}
		lena = gjj1(x1,lenx1,a,1ll);
		lenb = gjj1(x1,lenx1,b,-1ll);
		for(long long i = -3;i <= 0;++i){
			memset(yt,0,sizeof(yt));
			lenyt = gjj1(x1,lenx1,yt,i);
			lena = gjmul(lena,a,lenyt,yt,kq);
			for(int j = 0;j < lena;++j){
				a[j] = kq[j];
			}
		}
		lena = gjdiv(a,lena,kq,120);
		for(int i = 0;i < lena;++i){
			a[i] = kq[i];
		}
		memset(kq,0,sizeof(kq));
		for(long long i = -5;i <= -2;++i){
			memset(yt,0,sizeof(yt));
			lenyt = gjj1(x1,lenx1,yt,i);
			lenb = gjmul(lenb,b,lenyt,yt,kq);
			for(int j = 0;j < lenb;++j){
				b[j] = kq[j];
			}
		}
		lenb = gjdiv(b,lenb,kq,120);
		for(int i = 0;i < lenb;++i){
			b[i] = kq[i];
		}
		leny2 = gjj(lena,a,lenb,b,y2);
		for(int i = leny2 - 1;i >= 0;i--){
			if(i == leny2 - 1){
				printf("%lld",y2[i]);
				continue;
			}
			if(y2[i] >= 10000)printf("%lld",y2[i]);
			else if(y2[i] >= 1000)printf("0%lld",y2[i]);
			else if(y2[i] >= 100)printf("00%lld",y2[i]);
			else if(y2[i] >= 10)printf("000%lld",y2[i]);
			else printf("0000%lld",y2[i]);//注意高位补零 
		}
		printf("\n");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 

上一篇: 博弈论学习笔记

下一篇: NOI2007 货币兑换 Cash 【CDQ分治 斜率优化DP】

立即登录,发表评论
没有帐号?立即注册
0 条评论