【SEERC2018A】【XSY3319】Numbers

给你一个数 \(n\)，求有多少种方案能把 \(n\) 分成两个非零回文数 \((a,b)\) 之和。

　　两个方案不同当且仅当 \(a_1\neq a_2\)。

　　\(n\leq {10}^{18}\)

题解

　　枚举那些位进了位，然后分两种情况讨论：

　　1.两个回文数位数相等。可以直接计算方案数。

　　2.两个回文数位数不相等。可以枚举位数，构造方程，然后解出来。例如，记第一个回文数为 \((a_4a_3a_2a_1)_{10}\)，第二个回文数为 \((b_3b_2b_1)_{10}\)，\(n=(c_4c_3c_2c_1)_{10}\)。构造的方程为：

\[\begin{cases}
a_4&=c_4\\
a_3+b_3&=c_3\\
a_2+b_2&=c_2\\
a_1+b_1&=c_1\\
a_4&=a_1\\
a_3&=a_2\\
b_3&=b_1\\
\end{cases}
\]

　　记 \(m=\log_{10}n\)。

　　复杂度为 \(O(m^22^m)\)

　　如果你只枚举前面 \(\frac{m}{2}\) 位是否进位，可以做到 \(O(m^22^{\frac{m}{2}})\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<functional>

#include<cmath>

#include<vector>

#include<assert.h>

//using namespace std;

using std::min;

using std::max;

using std::swap;

using std::sort;

using std::reverse;

using std::random_shuffle;

using std::lower_bound;

using std::upper_bound;

using std::unique;

using std::vector;

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

typedef std::pair<int,int> pii;

typedef std::pair<ll,ll> pll;

void open(const char *s){

#ifndef ONLINE_JUDGE

	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);

#endif

}

void open2(const char *s){

#ifdef DEBUG

	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);

#endif

}

int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}

void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}

int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}

int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}

ll ans;

int t,t2;

int a[100];

int b[100];

ll n;

void gao1()

{

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

		if(b[i]!=b[t2-i+1])

			return;

	ll res=1;

	for(int i=1;i<=(t2+1)/2;i++)

		res*=min(9,(i==1?b[i]-1:b[i]))-max(b[i]-9,(i==1?1:0))+1;

	ans+=res;

}

int a1[100],a2[100];

void gao2()

{

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

	{

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

			a1[j]=a2[j]=0;

		for(int j=t2;j>i;j--)

			if(!a1[j])

			{

				int x=j;

				int v=b[j];

				while(!a1[x])

				{

					a1[x]=v;

					x=t2-x+1;

					a1[x]=v;

					if(a2[x])

						break;

					if(x>i)

						break;

					a2[x]=v=b[x]-a1[x];

					x=i-x+1;

					a2[x]=v;

					v=b[x]-a2[x];

				}

			}

		int flag=1;

		for(int j=1;flag&&j<=t2;j++)

			if(a1[j]<0||a1[j]>9||a1[j]+a2[j]!=b[j]||a1[t2-j+1]!=a1[j])

				flag=0;

		for(int j=1;flag&&j<=i;j++)

			if(a2[j]<0||a2[j]>9||a2[j]!=a2[i-j+1])

				flag=0;

		if(a2[i]==0)

			flag=0;

		if(flag)

			ans+=2;

	}

}

int main()

{

	open("number");

	scanf("%lld",&n);

	ll m=n;

	while(m)

	{

		a[++t]=m%10;

		m/=10;

	}

	for(int i=0;i<1<<(t-1);i++)

	{

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

			b[j]=a[j];

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

			if((i>>(j-1))&1)

			{

				b[j]+=10;

				b[j+1]--;

			}

		int flag=1;

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

			if(b[j]<0||b[j]>18)

			{

				flag=0;

				break;

			}

		if(!flag)

			continue;

		t2=t;

		while(!b[t2])

			t2--;

		gao1();

		gao2();

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

【SEERC2018A】【XSY3319】Numbers

题解

代码

最新文章

热门文章