#include<bits/stdc++.h>
using namespace std;
vector<int> num;
int dp[40005];
int t,n;
void f()
{
num.push_back(0);
int n,sum=0,i=1,p;
while(i<=40000)
{
p=i;
sum=0;
while(p>0)
{
sum=sum*10+p%10;
p=p/10;
}
if(i==sum) num.push_back(i);
i++;
}
return ;
}
int main()
{
f();
cin>>t;
for(int q=1;q<=t;q++)
{
cin>>n;
dp[0]=1;
for(int i=1;i<=n;i++)
{
dp[i]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=n-num[i];j++)
{
dp[j+num[i]]+=dp[j];
}
}
cout<<dp[n]<<endl;
}
}
题面
E. 回文之和
Problem ID: 15741
Contest ID: 5882
必做题
Runtime Error
题目描述
给你一个正整数
�
n，如果一个正整数(没有前导
0
0)反转后和原来相同，那么就称该数为一个回文整数。现在你要找到有多少种方案使得回文整数之和等于
�
n。如果两个方案中至少有一个回文整数不同，那么这两种方案是不同的。例：
5
4
+
1
5=4+1和
5
3
+
1
+
1
5=3+1+1是两种不同的方案，而
5
3
+
1
+
1
5=3+1+1和
5
1
+
3
+
1
5=1+3+1则是相同的。
由于答案可能巨大，请对
1
0
9
+
7
10
9
+7取模。
输入示例
多组数据，第一行输入一个正整数
�
(
1
≤
�
≤
1
0
4
)
t(1≤t≤10
4
)，表示测试数据组数。
对于每组测试数据，每行包含一个正整数
�
(
1
≤
�
≤
4
×
1
0
4
)
n(1≤n≤4×10
4
)，表示要求的回文整数之和。
输出示例
对于每组数据，输出一个对
1
0
9
+
7
10
9
+7取模的整数，表示方案数。
样例#1
输入样例#1
2
5
12
输出样例#1
7
74
样例说明
对于样例#1，一共有如下
7
7种方法：
5
1
+
1
+
1
+
1
+
1
5=1+1+1+1+1
5
1
+
1
+
1
+
2
5=1+1+1+2
5
1
+
2
+
2
5=1+2+2
5
1
+
1
+
3
5=1+1+3
5
2
+
3
5=2+3
5
1
+
4
5=1+4
5
5
5=5
对于样例#2，一共有
77
77种方法得到
12
12，但是
12
2
+
10
12=2+10，
12
12
12=12这种并不在有效方法内，因为
10
10和
12
12并不是回文整数。
