藍橋杯樣題_花朵數(shù)21（DFS剪枝+高精度)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll N=21;
const int NB=24;?
vector<int> add(vector<int> a, vector<int> b){
? ? vector<int> res(NB);
? ? int carr=0;
? ? for(int i=0;i<NB;i++){
? ? ? ? res[i]=a[i]+b[i]+carr;
? ? ? ? carr=0;
? ? ? ? if(res[i]>=10){
? ? ? ? ? ? carr=res[i]/10;
? ? ? ? ? ? res[i]=res[i]%10;
? ? ? ? }
? ? }
? ? return res;
}
vector<int> div10(vector<int> a){
? ? vector<int> res(NB);
? ? for(int i=NB-1;i>0;i--){
? ? ? ? res[i-1]=a[i];
? ? }
? ? return res;
}
int rem10(vector<int> a){
? ? return a[0];
}
vector<int>? multi(vector<int>? a, int c){
? ? vector<int>? res(NB);
? ? int carr=0;
? ? for(int i=0;i<NB;i++){
? ? ? ? res[i]=a[i]*c+carr;
? ? ? ? carr=0;
? ? ? ? if(res[i]>=10){
? ? ? ? ? ? carr=res[i]/10;
? ? ? ? ? ? res[i]=res[i]%10;
? ? ? ? }
? ? }
? ? return res;
}? ? ? ? ? ??
bool greatthanzero(vector<int> a){
? ? for(int i=0;i<NB;i++){
? ? ? ? if(a[i]>0){
? ? ? ? ? ? return true;
? ? ? ? }
? ? }? ??
? ? return false;
}? ??
int a[10]; // save digit 次數(shù)
vector< vector<int> >? c(10, vector<int> (NB)); //save 0-9 N次方
void check_print(vector<int> ps){
? ? int dig[10];
? ? memset(dig,0,sizeof(dig));
? ? bool leadingzero=true;
? ? for(int i=ps.size()-1;i>=0;i--){
? ? ? ? if(ps[i]>0){
? ? ? ? ? ? leadingzero=false;
? ? ? ? }
? ? ? ? if(!leadingzero){
? ? ? ? ? ? dig[ps[i]]++;
? ? ? ? }? ??
? ? }
? ? bool match=true;
? ? for(int i=0;i<10;i++){
? ? ? ? if(dig[i]!=a[i]){
? ? ? ? ? ? match=false;
? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? if(match){
? ? ? ? bool leadingzero=true;
? ? ? ? for(int i=ps.size()-1;i>=0;i--){
? ? ? ? ? ? if(ps[i]>0){
? ? ? ? ? ? ? ? leadingzero=false;
? ? ? ? ? ? }
? ? ? ? ? ? if(!leadingzero){
? ? ? ? ? ? ? ? cout<<ps[i];
? ? ? ? ? ? }? ??
? ? ? ? }
? ? ? ? cout<<endl;
? ? }? ??
}??
void printa(vector<int> a){
? ? for(int i=a.size()-1;i>=0;i--){
? ? ? ? cout<<a[i];
? ? }
? ? cout<<endl;
}? ??
? ??
? ? ? ??
void dfs(int i, int n, vector<int> ps){
? ? if(i==9||n==0){//枚舉最后一個數(shù)
? ? ? ? ps=add(ps,multi(c[i],n));
? ? ? ? a[i]=n;
? ? ? ? check_print(ps);
? ? ? ? return;? ? ? ? ? ? ? ??
? ? }? ??
? ? for(int j=0;j<=n;j++){
? ? ? ? if(i==0&&j==n){//首位不為0
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? a[i]=j;
? ? ? ? //cout<<i<<" "<<j<<" "<<nbb<<" "<<bmax<<" "<<ncb<<" "<<cmax<<endl;
? ? ? ? dfs(i+1,n-j,add(ps,multi(c[i],j)));
? ? }
}? ??
? ? ? ? ? ??
int main()
{
? ? c[1][0]=1;
? ? for(int i=2;i<=9;i++){
? ? ? ? vector<int> sj(NB);
? ? ? ? sj[0]=1;
? ? ? ? for(int j=1;j<=N;j++){
? ? ? ? ? ? sj=multi(sj,i);
? ? ? ? }
? ? ? ? c[i]=sj;
? ? ? ? printa(c[i]);
? ? }
? ? cout<<endl;
? ? vector<int> zero(NB);
? ? dfs(0,N,zero);
? ? return 0;
}
