各个位数上的数字都不相同的正整数
小明心中有一种美丽整数,这种数是指各个位数上的数字都不相同的正整数.例如:12345是美丽整数,121就不是美丽整数.
a 是某正整数,问闭区间内[1,a]有几个美丽整数.
样例a=10,则有10个
a=1000,有738个. 100以内,没有相同数码的正整数:[code]Select[Range[100],
FromDigits[DeleteDuplicates[IntegerDigits[#]]] == # &][/code]10000以内,没有相同数码的完全平方数:[code]Select[Range[100],
FromDigits[DeleteDuplicates[IntegerDigits[#^2]]] == #^2 &]^2[/code] 写出一个通式可能比较麻烦,但就具体的数来算还算容易,举个例:
[1,62485] 内的美丽整数中:
不超四位数的:9+9*9+9*9*8+9*9*8*7 个;
[1~5]xxxx 的:5*9*8*7*6 个;
6[0~1]xxx 的:2*8*7*6 个;
62[0~3]xx 的:3*7*6 个;
624[0~7]x 的:5*6 个;
6248[0~5] 的:4 个;
所以结果为:9 + 9*9 + 9*9*8 + 9*9*8*7 + 5*9*8*7*6 + 2*8*7*6 + 3*7*6 + 5*6 + 4 = 21226。 是的,通式要分很多类,暂时没找到好算法
小朋友编的,通过[code]#include<stdio.h>
using namespace std;
int h(int n,int m){
int H=1;
for(int i=0;i<m;i++,n--)H*=n;
return H;
}
int g(int n){
if(!n)return 0;
int a[10],num=0,G=0;
bool b[10]={1,1,1,1,1,1,1,1,1,1};
while(n){
num++;
a[num]=n%10;
n/=10;
}
for(int i=num;i>1;i--){
for(int j=!(num-i);j<a[i];j++)if(b[j])G+=h(10-num+i-1,i-1);
if(b[a[i]]){
b[a[i]]=0;
}
else return G;
}
for(int j=!(num-1);j<=a[1];j++)if(b[j])G++;
return G;
}
int t(int n){
int T=0;
int num=0,sum=9;
while(n>sum){
num++;
sum=sum*10+9;
T+=9*h(9,num-1);
}
return T;
}
int f(int n){
int F=0;
F+=t(n);
F+=g(n);
return F;
}
int main(){
int t;
scanf("%d",&t);
for(int i=0;i<t;i++){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",f(r)-f(l-1));
}
return 0;
}[/code] [b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=33479&ptid=6515]4#[/url] [i]realnumber[/i] [/b]
想了想其实写通式也不是很麻烦,也就两类情况。
求不超过 `\overline{a_1a_2\cdots a_n}`(`n\leqslant10`)的美丽整数个数。
记 `b_k` 为 `a_1` 至 `a_{k-1}` 当中小于 `a_k` 的个数(比如我在 3# 举的例子 `62485` 有 `b_2=0`, `b_3=1`, `b_4=3`, `b_5=2`)。
(1)若 `\overline{a_1a_2\cdots a_n}` 本身就是美丽整数,则所求个数为
\begin{align*}
&9(1+A_9^1+A_9^2+\cdots+A_9^{n-2})+(a_1-1)A_9^{n-1}\\
{}+{}&(a_2-b_2)A_8^{n-2}+(a_3-b_3)A_7^{n-3}+\cdots+(a_{n-1}-b_{n-1})A_{11-n}^1+a_n-b_n+1;
\end{align*}
(2)若 `\overline{a_1a_2\cdots a_n}` 不是美丽整数,设其在第 `m` 位首次出现重复数字(比如 `62685` 为 `m=3`),则所求个数为
\begin{align*}
&9(1+A_9^1+A_9^2+\cdots+A_9^{n-2})+(a_1-1)A_9^{n-1}\\
{}+{}&(a_2-b_2)A_8^{n-2}+(a_3-b_3)A_7^{n-3}+\cdots+(a_m-b_m)A_{10-m}^{n-m}.
\end{align*}
页:
[1]