bzoj 2552: Zju2253 Fill the Grid 高精度+打表

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2552

看到数据范围，直接就想打表，先写了发dfs暴搜，结果发现连 $5$ $5$ 的点都跑到天荒地老，然后就开始dp。

dp数组一共n维，第i维表示第i行放了几个数。

如果数据范围小一点的话，就可以开一个多维的dp数组，然后大力dp了，但是这个题的数据范围显然是不允许我们这么做的，所以再大胆一点，把9个map套在一起，然后里面再套一个高精度。

代码虽然很暴力，但是打表速度还是很快的。

打表程序：

#include<bits/stdc++.h>

#define bit bitset<110>
#define ll long long

using namespace std;

inline int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*y;
}
struct bn{
	#define MAXN 1010
	#define ll long long
	int len;
	char num[MAXN];
	bn(ll x){
		memset(num,0,sizeof(num));
		len=0;
		while(x>0){
			num[len++]=x%10;
			x/=10;
		}
	}
	bn(){memset(num,0,sizeof(num)),len=0;}
	void rd(){
		len=0;
		char c=getchar();
		while(!isdigit(c))c=getchar();
		while(isdigit(c))num[len++]=c-'0',c=getchar();
		for(int i=0; i<len/2; i++)swap(num[i],num[len-i-1]);
	}
	void out(){
		if(!len)printf("0");
		for(int i=len-1; i>=0; i--)printf("%d",num[i]);
	}
	void half(){
		for(int i=len-1; i>0; i--){
			num[i-1]+=(num[i]%2)*10;
			num[i]/=2;
		}
		num[0]/=2;
		while(len-1>=0 && !num[len-1])len--;
	}
	friend bn operator + (bn a,bn b){
		bn c;
		for(int i=0; i<a.len || i<b.len; i++){
			c.num[i]+=a.num[i]+b.num[i];
			c.num[i+1]+=c.num[i]/10;
			c.num[i]%=10;
		}
		c.len=max(a.len,b.len);
		if(c.num[c.len])c.len++;
		return c;
	}
	friend bn operator + (bn a,ll b){return a+bn(b);}
	friend bn operator + (ll a,bn b){return bn(a)+b;}
	friend bn operator - (bn a,bn b){
		bn c;
		for(int i=0; i<a.len; i++){
			c.num[i]+=a.num[i]-b.num[i];
			if(c.num[i]<0)c.num[i+1]--,c.num[i]+=10;
		}
		c.len=max(a.len,b.len);
		while(c.len-1>=0 && !c.num[c.len-1])c.len--;
		return c;
	}
	friend bn operator - (bn a,ll b){return a-bn(b);}
	friend bn operator * (bn a,bn b){
		bn c;
		for(int i=0; i<a.len; i++){
			for(int j=0; j<b.len; j++){
				c.num[i+j]+=a.num[i]*b.num[j];
				c.num[i+j+1]+=c.num[i+j]/10;
				c.num[i+j]%=10;
			}
		}
		c.len=a.len+b.len;
		while(c.len-1>=0 && !c.num[c.len-1])c.len--;
		return c;
	}
	friend bn operator * (bn a,ll b){return a*bn(b);}
	friend bn operator * (ll a,bn b){return bn(a)*b;}
	friend bool operator < (bn a,bn b){
		if(a.len!=b.len)return a.len<b.len;
		for(int i=a.len-1; i>=0; i--)if(a.num[i]!=b.num[i])return a.num[i]<b.num[i];
		return false;
	}
	friend bool operator == (bn a,bn b){
		if(a.len!=b.len)return false;
		for(int i=0; i<a.len; i++)if(a.num[i]!=b.num[i])return false;
		return true;
	}
	friend bool operator <= (bn a,bn b){
		return a<b || a==b;
	}
	friend bn operator / (bn a,bn b){
		bn c;
		bn l,r,mid;
		l=bn(0),r=a;
		while(l<=r){
			mid=l+r;
			mid.half();
			if(mid*b<=a)c=mid,l=mid+1;
			else r=mid-1;
		}
		return c;
	}
	friend bn operator % (bn a,bn b){
		return a-(b*(a/b));
	}
	friend bn operator ^ (bn x,ll y){
        bn z=1;
        while(y){
            if(y&1)z=z*x;
            x=x*x;
            y/=2;
        }
        return z;
    }
	#undef ll
	#undef MAXN
};

int n,m,ans;
int Max[11],a[11];
map<int,map<int,map<int,map<int,map<int,map<int,map<int,map<int,map<int,bn> > > > > > > > >f;

inline void init(int i,int j){
    f.clear();
    n=i,m=j;
    memset(Max,0,sizeof Max);
    for(int i=1; i<=n; i++)Max[i]=m;
}

void dfs(int deep,int num){
    if(deep==10){
        for(int i=1; i<=9; i++){
            if(a[i]){
                f[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]=f[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]+f[a[1]-(i==1)][a[2]-(i==2)][a[3]-(i==3)][a[4]-(i==4)][a[5]-(i==5)][a[6]-(i==6)][a[7]-(i==7)][a[8]-(i==8)][a[9]-(i==9)];
            }
        }
        return;
    }
    for(int i=0; i<=min(Max[deep],num); i++){
        a[deep]=i;
        dfs(deep+1,i);
    }
}

inline void work(){
    f[0][0][0][0][0][0][0][0][0]=1;
    dfs(1,m);
    printf("ans[%d][%d]=\"",n,m);
    f[Max[1]][Max[2]][Max[3]][Max[4]][Max[5]][Max[6]][Max[7]][Max[8]][Max[9]].out();
    cout<<"\";"<<endl;
}

int main(){
    for(int i=1; i<=9; i++){
        for(int j=1; j<=9; j++){
            init(i,j);
            if(n==0 && m==0)break;
            work();
        }
    }
    
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

#include<bits/stdc++.h>

#define bit bitset<110>

#define ll long long

using namespace std;

inline int rd(){

int x=0,y=1;char c=getchar();

while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}

while(isdigit(c))x=x*10+c-'0',c=getchar();

return x*y;

}

struct bn{

#define MAXN 1010

#define ll long long

int len;

char num[MAXN];

bn(ll x){

memset(num,0,sizeof(num));

len=0;

while(x>0){

num[len++]=x%10;

x/=10;

}

bn(){memset(num,0,sizeof(num)),len=0;}

void rd(){

len=0;

char c=getchar();

while(!isdigit(c))c=getchar();

while(isdigit(c))num[len++]=c-'0',c=getchar();

for(int i=0; i<len/2; i++)swap(num[i],num[len-i-1]);

}

void out(){

if(!len)printf("0");

for(int i=len-1; i>=0; i--)printf("%d",num[i]);

}

void half(){

for(int i=len-1; i>0; i--){

num[i-1]+=(num[i]%2)*10;

num[i]/=2;

}

num[0]/=2;

while(len-1>=0 && !num[len-1])len--;

}

friend bn operator + (bn a,bn b){

bn c;

for(int i=0; i<a.len || i<b.len; i++){

c.num[i]+=a.num[i]+b.num[i];

c.num[i+1]+=c.num[i]/10;

c.num[i]%=10;

}

c.len=max(a.len,b.len);

if(c.num[c.len])c.len++;

return c;

}

friend bn operator + (bn a,ll b){return a+bn(b);}

friend bn operator + (ll a,bn b){return bn(a)+b;}

friend bn operator - (bn a,bn b){

bn c;

for(int i=0; i<a.len; i++){

c.num[i]+=a.num[i]-b.num[i];

if(c.num[i]<0)c.num[i+1]--,c.num[i]+=10;

}

c.len=max(a.len,b.len);

while(c.len-1>=0 && !c.num[c.len-1])c.len--;

return c;

}

friend bn operator - (bn a,ll b){return a-bn(b);}

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

bn c;

for(int i=0; i<a.len; i++){

for(int j=0; j<b.len; j++){

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

c.num[i+j+1]+=c.num[i+j]/10;

c.num[i+j]%=10;

}

c.len=a.len+b.len;

while(c.len-1>=0 && !c.num[c.len-1])c.len--;

return c;

}

friend bn operator * (bn a,ll b){return a*bn(b);}

friend bn operator * (ll a,bn b){return bn(a)*b;}

friend bool operator < (bn a,bn b){

if(a.len!=b.len)return a.len<b.len;

for(int i=a.len-1; i>=0; i--)if(a.num[i]!=b.num[i])return a.num[i]<b.num[i];

return false;

}

friend bool operator == (bn a,bn b){

if(a.len!=b.len)return false;

for(int i=0; i<a.len; i++)if(a.num[i]!=b.num[i])return false;

return true;

}

friend bool operator <= (bn a,bn b){

return a<b || a==b;

}

friend bn operator / (bn a,bn b){

bn c;

bn l,r,mid;

l=bn(0),r=a;

while(l<=r){

mid=l+r;

mid.half();

if(mid*b<=a)c=mid,l=mid+1;

else r=mid-1;

}

return c;

}

friend bn operator % (bn a,bn b){

return a-(b*(a/b));

}

friend bn operator ^ (bn x,ll y){

bn z=1;

while(y){

if(y&1)z=z*x;

x=x*x;

y/=2;

}

return z;

}

#undef ll

#undef MAXN

};

int n,m,ans;

int Max[11],a[11];

map<int,map<int,map<int,map<int,map<int,map<int,map<int,map<int,map<int,bn> > > > > > > > >f;

inline void init(int i,int j){

f.clear();

n=i,m=j;

memset(Max,0,sizeof Max);

for(int i=1; i<=n; i++)Max[i]=m;

}

void dfs(int deep,int num){

if(deep==10){

for(int i=1; i<=9; i++){

if(a[i]){

f[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]=f[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]+f[a[1]-(i==1)][a[2]-(i==2)][a[3]-(i==3)][a[4]-(i==4)][a[5]-(i==5)][a[6]-(i==6)][a[7]-(i==7)][a[8]-(i==8)][a[9]-(i==9)];

}

return;

}

for(int i=0; i<=min(Max[deep],num); i++){

a[deep]=i;

dfs(deep+1,i);

}

inline void work(){

f[0][0][0][0][0][0][0][0][0]=1;

dfs(1,m);

printf("ans[%d][%d]=\"",n,m);

f[Max[1]][Max[2]][Max[3]][Max[4]][Max[5]][Max[6]][Max[7]][Max[8]][Max[9]].out();

cout<<"\";"<<endl;

}

int main(){

for(int i=1; i<=9; i++){

for(int j=1; j<=9; j++){

init(i,j);

if(n==0 && m==0)break;

work();

}

return 0;

}

AC程序：

#include<bits/stdc++.h>

using namespace std;

inline int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*y;
}

int n,m;
string ans[10][10];

inline void init(){
    ans[1][1]="1";
    ans[1][2]="1";
    ans[1][3]="1";
    ans[1][4]="1";
    ans[1][5]="1";
    ans[1][6]="1";
    ans[1][7]="1";
    ans[1][8]="1";
    ans[1][9]="1";
    ans[2][1]="1";
    ans[2][2]="2";
    ans[2][3]="5";
    ans[2][4]="14";
    ans[2][5]="42";
    ans[2][6]="132";
    ans[2][7]="429";
    ans[2][8]="1430";
    ans[2][9]="4862";
    ans[3][1]="1";
    ans[3][2]="5";
    ans[3][3]="42";
    ans[3][4]="462";
    ans[3][5]="6006";
    ans[3][6]="87516";
    ans[3][7]="1385670";
    ans[3][8]="23371634";
    ans[3][9]="414315330";
    ans[4][1]="1";
    ans[4][2]="14";
    ans[4][3]="462";
    ans[4][4]="24024";
    ans[4][5]="1662804";
    ans[4][6]="140229804";
    ans[4][7]="13672405890";
    ans[4][8]="1489877926680";
    ans[4][9]="177295473274920";
    ans[5][1]="1";
    ans[5][2]="42";
    ans[5][3]="6006";
    ans[5][4]="1662804";
    ans[5][5]="701149020";
    ans[5][6]="396499770810";
    ans[5][7]="278607172289160";
    ans[5][8]="231471904322784840";
    ans[5][9]="219738059326729823880";
    ans[6][1]="1";
    ans[6][2]="132";
    ans[6][3]="87516";
    ans[6][4]="140229804";
    ans[6][5]="396499770810";
    ans[6][6]="1671643033734960";
    ans[6][7]="9490348077234178440";
    ans[6][8]="67867669180627125604080";
    ans[6][9]="583692803893929928888544400";
    ans[7][1]="1";
    ans[7][2]="429";
    ans[7][3]="1385670";
    ans[7][4]="13672405890";
    ans[7][5]="278607172289160";
    ans[7][6]="9490348077234178440";
    ans[7][7]="475073684264389879228560";
    ans[7][8]="32103104214166146088869942000";
    ans[7][9]="2760171874087743799855959353857200";
    ans[8][1]="1";
    ans[8][2]="1430";
    ans[8][3]="23371634";
    ans[8][4]="1489877926680";
    ans[8][5]="231471904322784840";
    ans[8][6]="67867669180627125604080";
    ans[8][7]="32103104214166146088869942000";
    ans[8][8]="22081374992701950398847674830857600";
    ans[8][9]="20535535214275361308250745082811167425600";
    ans[9][1]="1";
    ans[9][2]="4862";
    ans[9][3]="414315330";
    ans[9][4]="177295473274920";
    ans[9][5]="219738059326729823880";
    ans[9][6]="583692803893929928888544400";
    ans[9][7]="2760171874087743799855959353857200";
    ans[9][8]="20535535214275361308250745082811167425600";
    ans[9][9]="220381378415074546123953914908618547085974856000";
}

int main(){
    init();
    while(1){
        int x=rd(),y=rd();
        if(x==0 && y==0)break;
        printf("%s\n",ans[x][y].c_str());
    }
    
    return 0;
}

100

101

102

103

104

105

106

107

108

#include<bits/stdc++.h>

using namespace std;

inline int rd(){

int x=0,y=1;char c=getchar();

while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}

while(isdigit(c))x=x*10+c-'0',c=getchar();

return x*y;

}

int n,m;

string ans[10][10];

inline void init(){

ans[1][1]="1";

ans[1][2]="1";

ans[1][3]="1";

ans[1][4]="1";

ans[1][5]="1";

ans[1][6]="1";

ans[1][7]="1";

ans[1][8]="1";

ans[1][9]="1";

ans[2][1]="1";

ans[2][2]="2";

ans[2][3]="5";

ans[2][4]="14";

ans[2][5]="42";

ans[2][6]="132";

ans[2][7]="429";

ans[2][8]="1430";

ans[2][9]="4862";

ans[3][1]="1";

ans[3][2]="5";

ans[3][3]="42";

ans[3][4]="462";

ans[3][5]="6006";

ans[3][6]="87516";

ans[3][7]="1385670";

ans[3][8]="23371634";

ans[3][9]="414315330";

ans[4][1]="1";

ans[4][2]="14";

ans[4][3]="462";

ans[4][4]="24024";

ans[4][5]="1662804";

ans[4][6]="140229804";

ans[4][7]="13672405890";

ans[4][8]="1489877926680";

ans[4][9]="177295473274920";

ans[5][1]="1";

ans[5][2]="42";

ans[5][3]="6006";

ans[5][4]="1662804";

ans[5][5]="701149020";

ans[5][6]="396499770810";

ans[5][7]="278607172289160";

ans[5][8]="231471904322784840";

ans[5][9]="219738059326729823880";

ans[6][1]="1";

ans[6][2]="132";

ans[6][3]="87516";

ans[6][4]="140229804";

ans[6][5]="396499770810";

ans[6][6]="1671643033734960";

ans[6][7]="9490348077234178440";

ans[6][8]="67867669180627125604080";

ans[6][9]="583692803893929928888544400";

ans[7][1]="1";

ans[7][2]="429";

ans[7][3]="1385670";

ans[7][4]="13672405890";

ans[7][5]="278607172289160";

ans[7][6]="9490348077234178440";

ans[7][7]="475073684264389879228560";

ans[7][8]="32103104214166146088869942000";

ans[7][9]="2760171874087743799855959353857200";

ans[8][1]="1";

ans[8][2]="1430";

ans[8][3]="23371634";

ans[8][4]="1489877926680";

ans[8][5]="231471904322784840";

ans[8][6]="67867669180627125604080";

ans[8][7]="32103104214166146088869942000";

ans[8][8]="22081374992701950398847674830857600";

ans[8][9]="20535535214275361308250745082811167425600";

ans[9][1]="1";

ans[9][2]="4862";

ans[9][3]="414315330";

ans[9][4]="177295473274920";

ans[9][5]="219738059326729823880";

ans[9][6]="583692803893929928888544400";

ans[9][7]="2760171874087743799855959353857200";

ans[9][8]="20535535214275361308250745082811167425600";

ans[9][9]="220381378415074546123953914908618547085974856000";

}

int main(){

init();

while(1){

int x=rd(),y=rd();

if(x==0 && y==0)break;

printf("%s\n",ans[x][y].c_str());

}

return 0;

}

everlasting

bzoj 2552: Zju2253 Fill the Grid 高精度+打表

发表评论取消回复

发表评论 取消回复

发表评论取消回复