思路:
对于长度为n的排列:
1 总的可能性是10^n
2 不含有0和9的可能性是8^n
3 只含有0的但不含有9的可能性:
∑ i = 1 n C n i × 8 n − i \sum_{i=1}^nC_n^i\times 8^{n-i} ∑i=1nCni×8n−i
4 只有9: 与0一样
5 最终答案由1减去2 3 4即可
注意:
求组合数的时候要乘以逆元
在设计减法的时候要加上mod
x的逆元:x^(mod-2)
预处理,提前求阶层
Ac代码:
#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e6+10;
using namespace std;
const int mod = 1e9+7;
LL f[N];
LL qpow(LL x,LL k)
{
LL res = 1;
while(k)
{
if(k&1) res=res*x%mod;
k>>=1;
x = x*x%mod;
}
return res;
}
LL C(LL n,LL m)
{
return f[n]*(qpow(f[m]*f[n-m]%mod,mod-2))%mod;
}
int main()
{
LL n;
f[0] = 1;
//注意预处理一下,f[n]代表n的阶层
for(int i=1;i<N;i++) f[i] = f[i-1]*i%mod;
cin>>n;
if(n<2)
{
cout<<0<<endl;
return 0;
}
//注意这里要加mod,不然会wa
LL ans = (qpow(10,n) - qpow(8,n)+mod)%mod;
LL tmp = 0;
for(LL i=1;i<=n;i++)
{
tmp = (tmp + C(n,i)%mod*qpow(8,n-i)%mod)%mod;
}
tmp = tmp%mod*2%mod;
//注意要加mod
ans = (ans - tmp + mod)%mod;
cout<<ans<<endl;
return 0;
}