题目描述
100 可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
样例
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
int n,ans;
bool check(int a,int c,int s)
{
long long b= (n-a)*(long long)c;
if(a == 0 || b == 0 || c == 0 ) return false;
while(b)
{
int x = b%10;
if(!x || (s>>x & 1)) return false;
s=s^(1<<(x));
b/=10;
}
for(int i=1;i<10;i++)
if( !(s >> i & 1) ) return false;
return true;
}
void dfs_c(int s,int a,int c)
{
if(check(a,c,s)){ ans++;//printf("%d %d\n",a,c);
}
for(int i=1;i<10;i++) if( ! (s>>i & 1) ) dfs_c(s^(1<<i),a,c*10+i);
}
/**
* s————表示状态,有哪些数被枚举了
* a————a的值是多少
* */
void dfs_a(int s,int a)
{
if( a >= n) return;
if(a) dfs_c(s,a,0);
for(int i=1;i<10;i++) if( ! (s>>i & 1) ) dfs_a(s^(1<<i),a*10+i);
}
int main(){
scanf("%d",&n);
dfs_a(0,0);
printf("%d",ans);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla