link

废话不多说，直接思路+题解。。。

思路

具体思路是计算出每一个数对总方案数的贡献方法数，然后求和就好了。比如n=4321：
1 的贡献值：很明显是1，只能有1这一种可能性。
2 的贡献值：注意在十位，所以贡献值应该是 $2∗9^1$
3 的贡献值：在百位，应该是 $3∗9^2$
4 的贡献值：在千位，应该是 $49^3$
所以某一个数的设位数为b，值为a
贡献值就是 $a9^{b-1}$
然而，如何去证明呢？
很简单，因为7不可用，每一位自然有9个选择
那么根据乘法原理，一位数随机排列为9种，两位数为81种，n位数就是 $9n9^n$9n 种，也就是 说，0-99999....9就可以用乘法原理来算，如果去掉0这种情况，再加上100000......0这 种情况，一加一减抵消了，总数没有变。就变成了1-100000......0的总数为 $a*9^b$种。

至此，我们就证明完了贡献值公式是正确的，但是，为什么总数是这些贡献值加起来呢？我们用位置原理 就能证明。还是之前那个例子，n=4321，计算出了4的贡献值，相当于我们已经算完了1......4000了，剩下无论如何千位数也不会变，相当于剩下三位的玩耍，那就可以转化为三位数321了。 计算完300以内的，我们又可以同理再次转化，直到转化到末尾为止。因此，贡献值就是他们的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <string>
#include<cmath>
using namespace std;
void count(long long n)
{
    //降次
     for(ans=0,k=1,cin>>n;n;k*=9,n/=10){
        int t=n%10;
        if(t>=7)t--;
        ans+=t*k;
    }
    cout<<ans<<endl;
    // 降次 未优化
    // long ans=0,k=1,minus=0;
    // while(n>=10){
    //     int t=n%10;
    //     if(t>=7)t--;
    //     ans+=t*pow(9,k-1);
    //     k++;
    //     n/=10;
    // }
    // if(n>=7)n--;
    // ans+=n*pow(9,k-1);
    // cout<<ans<<endl;
        
/*3 TLE*/
    // int ans = 0;
    // for (int i = 1; i <= n; ++i)
    // {
    //     int t = i, flag = 0;
    //     while (t >= 10)
    //         if (t % 10 != 7)
    //             t /= 10;
    //         else
    //         {
    //             flag = 1;
    //             break;
    //         }
    //     if (t == 7 || flag)
    //         ans++;
    // }
    // cout << (n - ans) << endl;
}
int main()
{
    int t;
    long long n;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        cin >> n;
        count(n);
    }
    return 0;
}

未优化代码中

1
2
3
4
5
6
7
8
9
10
11
long ans=0,k=1,minus=0;
while(n>=10){
    int t=n%10;
    if(t>=7)t--;
    ans+=t*pow(9,k-1);
    k++;
    n/=10;
}
if(n>=7)n--;//一开始没加
ans+=n*pow(9,k-1);
cout<<ans<<endl;

因为那个低级错误，浪费了我好长时间。
没加的话少了一个7的过滤。

贴上最简代码。

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>//万能头
using namespace std;//。
long long n,T,ans,atr;//n一定会很大，so我开了long long.
int main(){
    cin>>T;//输入组数
    while(T--){//在组数这方面，while比for好用。
        for(atr=1,ans=0,scanf("%lld",&n);n;n/=10,atr*=9)//初始化变量直接装进for，很方便
            ans+=atr*(n%10)-(n%10>=7?atr:0);//特判>=7的情况
        cout<<ans<<endl;//输出答案
    }
    return 0;
}