COGS 2162 [NERRC2003][POJ1608]angry的蛤

【题目描述】
ZLX有2*N只蛤。由于个人爱好,他在每只蛤上都写了一个0到9的数字。他现在让着2*N只蛤排成了一列,如果前N只蛤的乘积和后N只蛤的乘积相等,则他称这列蛤为exciting的,反之则是angry的。由于某些蛤上的数字已经看不清楚了,他需要再在这些蛤上写上0到9。
他现在想知道,有多少种写法可以使这列蛤为exciting的。有多少种写法使这列蛤为angry。
【输入格式】
第一行为N(1<=N<=18).
之后的一行有N个字符,如果字符为?,说明这个数字看不清了。
【输出格式】
第一行输出有多少种方案可以使这列蛤为exciting
第二行输出有多少种方法可以使这列蛤为angry
【样例输入】
2
2??3
【样例输出】
4
96
【提示】
【来源】
【题目来源】
题面有所改动
POJ1608

这OJ吃枣药丸。。。。。
先抄码填坑(((((((

#include<cstdio>
#include<map>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
typedef long long LL;
using namespace std;
const int BASE=10000000;
char str[40];
class miku
{
public:
	int n;
	LL s[8];
	miku()
	{
		n=1;memset(s,0,sizeof(s));
	}
	void inline operator =(const int a)
	{
		n=1;
		memset(s,0,sizeof(s));
		s[0]=a;
	}
	void inline operator +=(const miku a)
	{
		n=max(n,a.n)+1;
		for(int i=0;i<min(n,a.n);i++)
		{
			s[i]+=a.s[i];
			while(s[i]<0) 
			{
				s[i]+=BASE;
				s[i+1]--;
			}
			s[i+1]+=s[i]/BASE;
			s[i]%=BASE;
		}
		while(n>1&&s[n-1]==0) n--;
	}
	bool inline operator ==(const int a)
	{
		if(n==1&&s[0]==a) return 1;
		return 0;
	}
	void print()
	{
		printf("%d",s[n-1]);
		for(int i=n-2;i>=0;i--) printf("%07d",s[i]);
		printf("\n");
	}
};
inline miku operator *(miku a,miku b)
{
	miku c;
	c.n=a.n+b.n+1;
	for(int i=0;i<=a.n;i++)
	{
		for(int j=0;j<=b.n;j++) 
		{
			c.s[i+j]+=a.s[i]*b.s[j];
			c.s[i+j+1]+=c.s[i+j]/BASE;
			c.s[i+j]%=BASE;
		}
	}
	while(c.n>1&&!c.s[c.n-1]) c.n--;
	return c;
}
LL s[70000];
miku pow10[40];
bool co[60][40][20][20]={0};
int cnt=0,N;
map<LL,miku> mp[2][2];
vector<LL> q[2];
int pos=0;
LL sb=1;
int cl(int x,int y)
{
	int ans=0;
	while(x%y==0)
	{
		ans++;
		x/=y;
	}
	return ans;
}
void bfs(int x,int y,int z,int p,LL now)
{
	if(co[x][y][z][p]) return;
	co[x][y][z][p]=1;
	s[++cnt]=now;
	for(int i=2;i<=9;i++)
	{
		if(now*i<=sb) bfs(x+cl(i,2),y+cl(i,3),z+cl(i,5),p+cl(i,7),now*i);
	}
}
void DP(int x)
{
	int i,m;
	if(x==0) i=1,m=N;
	else i=N+1,m=2*N;
	int be=0,k=0;
	q[be].clear();
	for(;i<=m;i++)
	{
		k=be^1;
		char c=str[i-1];
		mp[x][k].clear();
		q[k].clear();
		if(c=='0')
		{
			for(int j=0;j<q[be].size();j++) mp[x][k][0]+=mp[x][be][q[be][j]];
			if(i==1||i==N+1) mp[x][k][0]=1;
			q[k].push_back(0);
		}
		else if('1'<=c&&c<='9')
		{
			LL	p=c-'0';
			for(int j=0;j<q[be].size();j++) 
			{
				LL tem=q[be][j];
				mp[x][k][p*tem]+=mp[x][be][tem];
				q[k].push_back(p*tem);
			}
			if(i==1||i==N+1) mp[x][k][p]=1,q[k].push_back(p);
			//cout<<x<<" "<<k<<" "<<q[k].size()<<" "<<mp[x][k][p]<<endl;
		}
		else if(c=='?')
		{
			for(int j=0;j<=9;j++)
			{
				if(i==1||i==N+1)
				{
					if(mp[x][k][j]==0) q[k].push_back(j);
					mp[x][k][j]=1;
				}
				for(int mo=0;mo<q[be].size();mo++)
				{
					LL tem=q[be][mo];
					if(mp[x][k][j*tem]==0) q[k].push_back(j*tem);
					mp[x][k][j*tem]+=mp[x][be][tem];
				}
			}
			pos++;
		}
		be=k;
		//cout<<q[k].size()<<endl;
	}
}
int main()
{
	freopen("banalticket.in","r",stdin);
	freopen("banalticket.out","w",stdout);
	pow10[0]=1;
	miku tem;
	tem=10;
	pow10[1]=pow10[0]*tem;
	for(int i=1;i<=36;i++) pow10[i]=pow10[i-1]*tem;
	scanf("%d",&N);
	for(int i=1;i<=N;i++) sb*=10;
	scanf("%s",str);
	s[0]=0;
	bfs(0,0,0,0,1);
	DP(0);DP(1);
	miku ans;
	ans=0;
	int p=N&1;
	/*for(int i=0;i<=cnt;i++)
	{
		cout<<s[i]<<" "<<mp[0][p][s[i]]<<" "<<mp[1][p][s[i]]<<endl;
	}*/
	for(int i=0;i<=cnt;i++) ans+=mp[0][p][s[i]]*mp[1][p][s[i]];
	//cout<<cnt<<endl;
	ans.print();
	tem=-1;
	ans=ans*tem;
	miku ans2;
	ans2=ans;
	ans2+=pow10[pos];
	ans2.print();
	return 0;
}

 

此条目发表在COGS, DP, POJ分类目录。将固定链接加入收藏夹。