「泉七培训 – 郑予凡」致命漏洞

2014年6月14日3,3870

对于55%的数据，此题可以用个简单的矩阵乘法

100%只要加上高精度即可，但是考场上高精度打萎了只有55%…

没发现挂哪了。。。

//orz yuwan
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long
using namespace std;
int ans[205],lans;
int n[205],ln;
int x,T;
int c[110],a[110][110],b[110][110];
void mul1(int a[110][110],int b[110][110],int c[110][110])
{
	int tmp[110][110];
	for(int i=1;i<=T;i++)
	    for(int j=1;j<=T;j++)
	    {
			tmp[i][j]=0;
			for(int k=1;k<=T;k++)
			    tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%2;
		}
	for(int i=1;i<=T;i++)
	    for(int j=1;j<=T;j++)
	        c[i][j]=tmp[i][j];
}
void mul2(int a[110],int b[110][110],int c[110])
{
	int tmp[110];
	    for(int j=1;j<=T;j++)
	    {
			tmp[j]=0;
			for(int k=1;k<=T;k++)
			    tmp[j]=(tmp[j]+a[k]*b[k][j])%2;
		}
	    for(int j=1;j<=T;j++)
	        c[j]=tmp[j];
}
void div()
{
	for(int i=1;i<=ln;i++)
	    {if(n[i]&1)n[i-1]+=5;n[i]>>=1;}
	while(ln&&!n[ln])ln--;
}
void update(int x)
{
	int a[205],la=1;
	memset(a,0,sizeof(a));
	a[1]=1;
	for(int i=1;i<=x;i++)
	{
	    for(int j=1;j<=la;j++)
	        a[j]<<=1;
	    for(int j=1;j<=la;j++)
	        {a[j+1]+=a[j]/10;a[j]%=10;if(a[la+1])la++;}
	}
	lans=max(la,lans);
	for(int i=1;i<=la;i++)
	    ans[i]+=a[i];
	for(int j=1;j<=lans;j++)
	    {ans[j+1]+=ans[j]/10;ans[j]%=10;if(ans[lans+1])lans++;}
}
int main()
{
	//freopen("bug.in","r",stdin);
	//freopen("bug.out","w",stdout);
	char ch[110];
	scanf("%s%d%d",ch,&T,&x);
	ln=strlen(ch);
	for(int i=1;i<=ln;i++)
	    n[ln-i+1]=ch[i-1]-'0';
	for(int i=1;i<T;i++)
	    b[i][i+1]=1;
	for(int i=1;i<=T;i++)
	{
	    if(x&1)b[T][i]=1;
	    x>>=1;
	}
	for(int i=1;i<=T;i++)
	    a[i][i]=1;
	while(ln)
	{
		if(n[1]&1)mul1(a,b,a);
		div();
		mul1(b,b,b);
	}
	c[1]=1;
	mul2(c,a,c);
	for(int i=1;i<=T;i++)
	    if(c[i])update(i-1);
	for(int i=lans;i;i--)
	    printf("%d",ans[i]);
	fclose (stdout);
	return 0;
}

//orz yuwan

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#define ll long long

using namespace std;

int ans[205],lans;

int n[205],ln;

int x,T;

int c[110],a[110][110],b[110][110];

void mul1(int a[110][110],int b[110][110],int c[110][110])

{

int tmp[110][110];

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

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

{

tmp[i][j]=0;

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

tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%2;

}

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

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

c[i][j]=tmp[i][j];

}

void mul2(int a[110],int b[110][110],int c[110])

{

int tmp[110];

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

{

tmp[j]=0;

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

tmp[j]=(tmp[j]+a[k]*b[k][j])%2;

}

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

c[j]=tmp[j];

}

void div()

{

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

{if(n[i]&1)n[i-1]+=5;n[i]>>=1;}

while(ln&&!n[ln])ln--;

}

void update(int x)

{

int a[205],la=1;

memset(a,0,sizeof(a));

a[1]=1;

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

{

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

a[j]<<=1;

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

{a[j+1]+=a[j]/10;a[j]%=10;if(a[la+1])la++;}

}

lans=max(la,lans);

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

ans[i]+=a[i];

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

{ans[j+1]+=ans[j]/10;ans[j]%=10;if(ans[lans+1])lans++;}

}

int main()

{

//freopen("bug.in","r",stdin);

//freopen("bug.out","w",stdout);

char ch[110];

scanf("%s%d%d",ch,&T,&x);

ln=strlen(ch);

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

n[ln-i+1]=ch[i-1]-'0';

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

b[i][i+1]=1;

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

{

if(x&1)b[T][i]=1;

x>>=1;

}

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

a[i][i]=1;

while(ln)

{

if(n[1]&1)mul1(a,b,a);

div();

mul1(b,b,b);

}

c[1]=1;

mul2(c,a,c);

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

if(c[i])update(i-1);

for(int i=lans;i;i--)

printf("%d",ans[i]);

fclose (stdout);

return 0;

}

« 「BZOJ2510」弱题「BZOJ1754」[Usaco2005 qua] Bull Math »

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

「泉七培训 – 郑予凡」致命漏洞

分类目录

热门文章

Myfriends

近期评论