题意
问[0,n]有多少个7
解析
先预处理9，99，999含有7的个数 从个位枚举 分三种情况 <7 只有99的含有7的个数 =7 要考虑99的含有7的个数 由于该位为7，就会产生sum个7 >7 要考虑99的含有7的个数 由于该位要经过7，就会产生pow(10,i)个7
题目链接
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define F first
#define S second
#define endl "\n"
#define eps 1e-6
#define base 131
#define lowbit(x) (x&(-x))
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define MAXN 0x7fffffff
#define INF 0x3f3f3f3f3f3f3f3f
#define ferma(a,b) pow(a,b-2)
#define mod(x) (x%mod+mod)%mod
#define pb push_back
#define decimal(x) cout << fixed << setprecision(x);
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define memset(a,b) memset(a,b,sizeof(a));
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std
;
template
<typename T
> inline T
fetch(){T ret
;cin
>> ret
;return ret
;}
template
<typename T
> inline vector
<T
> fetch_vec(int sz
){vector
<T
> ret(sz
);for(auto& it
: ret
)cin
>> it
;return ret
;}
template
<typename T
> inline void makeUnique(vector
<T
>& v
){sort(v
.begin(), v
.end());v
.erase(unique(v
.begin(), v
.end()), v
.end());}
void file()
{
#ifdef ONLINE_JUDGE
#else
freopen("D:/LSNU/codeforces/duipai/data.txt","r",stdin);
#endif
}
const int N
=1e5+5;
const int mod
=1e9+7;
int dp
[N
];
int pow(int a
,int b
)
{
int ans
=1;
while(b
)
{
if(b
&1)
ans
=ans
*a
%mod
;
b
>>=1;
a
=a
*a
%mod
;
}
return ans
;
}
signed main()
{
IOS
;
file();
for(int i
=1;i
<=1e5;i
++)
dp
[i
]=(dp
[i
-1]*10%mod
+pow(10ll,i
-1))%mod
;
int t
;
cin
>>t
;
while(t
--)
{
string str
;
cin
>>str
;
int n
=str
.size();
int ans
=0,sum
=0;
reverse(all(str
));
for(int i
=0;i
<n
;i
++)
{
int pos
=str
[i
]-'0';
if(pos
<7)
{
ans
=(ans
+pos
*dp
[i
]%mod
)%mod
;
}
else if(pos
==7)
{
ans
=(ans
+pos
*dp
[i
]%mod
+sum
+1)%mod
;
}
else
{
ans
=(ans
+pos
*dp
[i
]%mod
+pow(10ll,i
))%mod
;
}
sum
=(sum
+pos
*pow(10ll,i
))%mod
;
}
cout
<<ans
<<endl
;
}
return 0;
}
