免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 各个位数上的数字都不相同的正整数

小明心中有一种美丽整数,这种数是指各个位数上的数字都不相同的正整数.
例如:12345是美丽整数,121就不是美丽整数.
a 是某正整数,问闭区间内[1,a]有几个美丽整数.
样例a=10,则有10个
a=1000,有738个.
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

100以内,没有相同数码的正整数:
  1. Select[Range[100],
  2. FromDigits[DeleteDuplicates[IntegerDigits[#]]] == # &]
复制代码
10000以内,没有相同数码的完全平方数:
  1. Select[Range[100],
  2.   FromDigits[DeleteDuplicates[IntegerDigits[#^2]]] == #^2 &]^2
复制代码

TOP

写出一个通式可能比较麻烦,但就具体的数来算还算容易,举个例:
[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。
1

评分人数

TOP

是的,通式要分很多类,暂时没找到好算法
小朋友编的,通过
  1. #include<stdio.h>
  2. using namespace std;

  3. int h(int n,int m){
  4.         int H=1;
  5.         for(int i=0;i<m;i++,n--)H*=n;
  6.         return H;
  7. }

  8. int g(int n){
  9.         if(!n)return 0;
  10.         int a[10],num=0,G=0;
  11.         bool b[10]={1,1,1,1,1,1,1,1,1,1};
  12.         while(n){
  13.                 num++;
  14.                 a[num]=n%10;
  15.                 n/=10;
  16.         }
  17.         for(int i=num;i>1;i--){
  18.                 for(int j=!(num-i);j<a[i];j++)if(b[j])G+=h(10-num+i-1,i-1);
  19.                 if(b[a[i]]){
  20.                         b[a[i]]=0;
  21.                 }
  22.                 else return G;
  23.         }
  24.         for(int j=!(num-1);j<=a[1];j++)if(b[j])G++;
  25.         return G;
  26. }

  27. int t(int n){
  28.         int T=0;
  29.         int num=0,sum=9;
  30.         while(n>sum){
  31.                 num++;
  32.                 sum=sum*10+9;
  33.                 T+=9*h(9,num-1);
  34.         }
  35.         return T;
  36. }

  37. int f(int n){
  38.         int F=0;
  39.         F+=t(n);
  40.         F+=g(n);
  41.         return F;
  42. }

  43. int main(){
  44.         int t;
  45.         scanf("%d",&t);
  46.         for(int i=0;i<t;i++){
  47.                 int l,r;
  48.                 scanf("%d%d",&l,&r);
  49.                 printf("%d\n",f(r)-f(l-1));
  50.         }
  51.         return 0;
  52. }
复制代码

TOP

回复 4# realnumber

想了想其实写通式也不是很麻烦,也就两类情况。

求不超过 `\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*}

TOP

返回列表 回复 发帖