题解：洛谷P1149 [NOIP2008 提高组] 火柴棒等式 加强版！！！

洛谷の原版，原题n<=24，暴力即可，本题n<=30000。

内存限制：128 MiB

时间限制：3000 ms

给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：

img

注意：

1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
3. n根火柴棍必须全部用上

答案对 1000000007 取模输出

n <= 30000

---

思路

为了达成复杂度 $O(\mathrm{可}\mathrm{过})$，考虑类似数位dp的写法，对A和B按位考虑，再求得C，总体分为以下几个部分：

1. 考虑有没有进位
2. 考虑A或者B是不是在这一位到达最高位（以免接下来的前导0耗费火柴，导致错误）
3. 考虑A或者B是不是0，即目前是不是最低位（用bool值可以为dp数组省去一个30000的位，防止MLE）

即可写出数位dp的dfs框架：（是否为最低位，A结束，B结束，进位，剩余火柴）

int dfs: bool zero, bool enda, bool endb, bool carry, int sum:
	if enda and endb: 
		if !sum and !carry or sum==2 and carry : return 1
		return 0
		
	for a 0...9:
		if enda and a : continue
		for b 0...9:
			if endb and b : continue
			c=(a+b+carry)%10,ncarry=(a+b+carry)/10
			nsum=sum-(matches used by a,b,c)
			
			zero=0
			if !enda and !endb:
				dfs in now
				if a can be cut: dfs in enda=1
				if b can be cut: dfs in endb=1
				if both can be cut: dfs in enda=endb=1
			else if !endb:
				dfs in now
				if b can be cut: dfs in endb=1
			else if !enda:
				dfs in now
				if a can be cut: dfs in enda=1
			else:
				dfs in now

	dp[sum][zero][enda][endb][carry]=dfs's sum
	return dfs's sum

非常的简单，直接代码

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod=1000000007;

ll n;
ll match[]={6,2,5,5,4,5,6,3,7,6}; // matches of 0...9

ll dp[30005][2][2][2][2];

ll dfs(bool zero,bool enda,bool endb,bool carry,ll sum)
{
	if(dp[sum][zero][enda][endb][carry]!=-1)
	{
		return dp[sum][zero][enda][endb][carry];
	}
	
	if(enda&&endb)
	{
		if((sum==0&&!carry)||(sum==2&&carry))
		{
			return 1;
		}
		return 0;
	}
	
	ll ret=0;
	
	for(ll a=0;a<10;a++)
	{
		if(enda&&a)
		{
			continue;
		}
		
		for(ll b=0;b<10;b++)
		{
			if(endb&&b)
			{
				continue;
			}
			
			ll c=a+b+carry;
			ll ncarry=c/10;
			c=c%10;
			
			ll nsum=sum-match[c];
			if(!enda)
			{
				nsum-=match[a];
			}
			if(!endb)
			{
				nsum-=match[b];
			}
			if(nsum<0)
			{
				continue;
			}
			
			bool cuta=(a!=0||(a==0&&zero==1)); //a can be cut
			bool cutb=(b!=0||(b==0&&zero==1)); //b can be cut
			
			if(!enda&&!endb)
			{
				ret=(ret+dfs(0,0,0,ncarry,nsum))%mod;
				if(cuta)
				{
					ret=(ret+dfs(0,1,0,ncarry,nsum))%mod;
				}
				if(cutb)
				{
					ret=(ret+dfs(0,0,1,ncarry,nsum))%mod;
				}
				if(cuta&&cutb)
				{
					ret=(ret+dfs(0,1,1,ncarry,nsum))%mod;
				}
			}
			else if(enda&&!endb)
			{
				ret=(ret+dfs(0,1,0,ncarry,nsum))%mod;
				if(cutb)
				{
					ret=(ret+dfs(0,1,1,ncarry,nsum))%mod;
				}
			}
			else if(!enda&&endb)
			{
				ret=(ret+dfs(0,0,1,ncarry,nsum))%mod;
				if(cuta)
				{
					ret=(ret+dfs(0,1,1,ncarry,nsum))%mod;
				}
			}
			else if(enda&&endb)
			{
				ret=(ret+dfs(0,1,1,ncarry,nsum))%mod;
			}
		}
	}
	
	ret%=mod;
	
	dp[sum][zero][enda][endb][carry]=ret;
	
	return ret;
}
 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	memset(dp,-1,sizeof dp);

	cin>>n;
	cout<<dfs(1,0,0,0,n-4)<<"\n"; //"+" and "=" cost 4 matches
	
	return 0;
}

---

样例

找不到其他可以测的地方，两个样例：

样例输入1

30000

样例输出1

75143404

样例输入2

20000

样例输出2

990516656