1.题目描述：
给你n根火柴棍，你可以拼出多少个形如“A+B=CA+B=C”的等式？等式中的AA、BB、CC是用火柴棍拼出的整 数（若该数非零，则最高位不能是00）。用火柴棍拼数字0-90−9的拼法如图所示:(我直接把对应的火柴 数写出来了) 6,2,5,5,4,5,6,3,7,6 注意 加号与等号各自需要两根火柴棍 如果a！=b则A+B=CA+B=C与B+A=CB+A=C视为不同的等式(A,B,C>=0A,B,C>=0) nn根火柴棍必须全部用上 输入格式： 一个整数n(n<=24)n(n<=24)。 输出格式： 一个整数，能拼成的不同等式的数目。 输入输出样例 输入 #1复制 14 输出 #1复制 2 输入 #2复制 18 输出 #2复制 9 说明/提示： 【输入输出样例1解释 22个等式为0+1=10+1=1和1+0=11+0=1 【输入输出样例2解释】 99个等式为： 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11
分析：
结合下面的代码，我们慢慢分析，首先看备注释的部分代码，这部分代表直接计算0-24每一项所用到的火 柴数，内层的循环中，1000的由来：按火柴数最少1111+1=1112在这时候所用到的数目是25，不符合范 围，所以说4位数肯定不满足，所以我们a或者b的值遍历到1000就足够了。然后看下面代码的注释。 等到输出完之后，直接打表，就是下面的arr[25]； 然后题目中输入a，就输出arr[a]。然后这道题就ac了。
源码：
#include <iostream> using namespace std; int pre[]={6,2,5,5,4,5,6,3,7,6}; int arr[25]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,88,128}; int main(void) { int n; cin>>n; cout<<arr[n]<<endl; // for(int n=0;n<=24;n++) // { // int arr=0; // for(int i=0;i<=1000;i++) // { // for(int j=0;j<=1000;j++) // { // int sum=0; // int a=i,b=j,c=i+j; // if(a==0) sum+=6; //因为a或b或c为零时，不会进入while循环中 // if(b==0) sum+=6; // if(c==0) sum+=6; // while(a) // {//这个循环中就是基本的每位用到的火柴数 // sum+=pre[a%10]; // a=a/10; // } // while(b) // { // sum+=pre[b%10]; // b=b/10; // } // while(c) // { // sum+=pre[c%10]; // c=c/10; // } // if(sum==n-4)//sum没有算加号和等号一共4根。 // { // arr++; // } // } // } // cout<<arr<<',';//输出每一项的火柴数所能配成的等式。 // } return 0; }
2.题目：
给定n个数，让你求这n个数的阶乘和对1e9+7取余为多少？ 1<=n<=1e6 1<=a[i]<=1e5
分析：
直接计算的时间复杂度为O（n*m），其中m为max（a[i]），即1e11.
解决办法：
1.那没一个数的阶乘给存下来，a[i]代表的是i的阶乘对mod取余的结果。 2.可以通过O(max(a[i]))的时间复杂度求解出所有数的阶乘并存到a数组里。 3.对于每一次，我们输入x，那么对应的阶乘值就是a[x]。 4.这样实现每一次计算的复杂度为O(1)。 5.总体时间复杂度为O(n+max(a[i]))。
源码：
#include <iostream> using namespace std; const int mod=1e9+7; const int maxn=1e5+9; long long pre[maxn]; int main() { pre[1]=1; for(int i=2;i<=100000;i++) { pre[i]=pre[i-1]*i; pre[i]=pre[i]%mod; } int n; cin>>n; long long ans=0; while(n--) { int x; cin>>x; ans+=pre[x]; ans%=mod; } cout<<ans<<endl; return 0; }
