数字8

不超过N位的正整数中包含有多少数字8？

输入格式
一行1个正整数N，范围[1,16]。

输出格式
一个整数。

• 既然计算数字8的数量不好算，那我们就反着来，计算没8的

• 现在开始推理：
  一个8：1C(n,1)9^(n-1)

  C(n,1)->n位数中，选一个当8
  9^(n-1)->剩下n-1位，每一位9种选择

  两个8：2C(n,2)9^(n-2)
  两个8：3C(n,3)9^(n-3)
  ......
  i个8：iC(n,i)9^(n-i)

#include<bits/stdc++.h>
using namespace std;

long long f(int x) {
    long long t=1;
    for(int i=1;i<=x;i++){
        t*=i;
    }
    return t;
}

long long c(int m, int n) {
    return f(m)/(f(n)*f(m-n));
}

int main() {
    int n;
    cin>>n;
    long long s=0;
    for(int i=1; i<=n; i++) {
        long long C=c(n,i);
        long long x=i*C*pow(9, n-i);
        s+=x;
    }
    cout<<s;
    return 0;
}