这题哈,
思路十分滴煎蛋哈
用k二维数组来存储“有零有九”“无零有九”“有零无九”“无零无九”的可能
(记得边处理边mod)
最后,输出!
代码实现如下:(严禁抄袭!!!)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=1000000007;
int f[1000001][4];
signed main(){
int n;
cin>>n;
f[1][0]=8;//0:X 9:X
f[1][1]=1;//0:√9:X
f[1][2]=1;//0:X 9:√
f[1][3]=0;//0:√9:√
for(int i=2;i<=n;i++){
f[i][0]=(f[i-1][0]*8)%P;
f[i][1]=(f[i-1][1]*9+f[i-1][0]*1)%P;
f[i][2]=(f[i-1][2]*9+f[i-1][0]*1)%P;
f[i][3]=(f[i-1][3]*10+f[i-1][2]*1+f[i-1][1]*1)%P;
}
cout<<f[n][3];
return 0;
}