ABC114 755
問題
方針
ABC119 Synthetic Kadomatsuと似ていたので、DFSで実装した。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<long long> VLL; typedef vector<pair<int,int>> VP; #define INF (int)(1e9) #define MAXX 1.1529215e+18 #define inf 999999 #define EPS (1e-7) #define MOD (1e9+7) #define rep(i,n) for(int i=0; i<(int)(n);i++) #define REP(i,n) for(int i=1;i<=(int)(n);i++) #define FOR(i,k,n) for(int i=(k);i<(int)(n);i++) #define ALL(a) a.begin(),a.end() #define RALL(a) a.begin(),a.end(),greater<int>() #define ROT(a) a.begin(),a.begin()+1,a.end() #define RROT(a) a.begin(),a.end()-1,a.end() #define PB push_back #define MP make_pair #define PI acos(-1.0) template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; } template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; } template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); } /*--------------------------------------------*/ ll n; int dim; int ans = 0; void dfs(int d,int x,int c3,int c5,int c7,int c0){ if(d == dim){ if(x <= n && c3*c5*c7 != 0){ ans++; } }else{ if(c0==d) dfs(d+1,0,c3,c5,c7,c0+1); dfs(d+1,10*x+3,c3+1,c5,c7,c0); dfs(d+1,10*x+5,c3,c5+1,c7,c0); dfs(d+1,10*x+7,c3,c5,c7+1,c0); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; dim = to_string(n).size(); dfs(0,0,0,0,0,0); cout << ans << endl; }
dfsの引数が少し汚い...。