제출 #270461

#제출 시각아이디문제언어결과실행 시간메모리
270461eohomegrownappsLucky Numbers (RMI19_lucky)C++14
28 / 100
3 ms1280 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll arr[100000]; ll m = 1000000007; ll n; ll dp[2][2][100000]; ll f(int ind, bool isEq, bool was1){ //cout<<ind<<' '<<isEq<<' '<<was1<<'\n'; if (ind==n){ return 1; } if (dp[isEq][was1][ind]!=-1){return dp[isEq][was1][ind];} ll tot = 0; for (int i = 0; i<=(isEq?arr[ind]:9); i++){ if (was1 && i==3){continue;} tot+=f(ind+1,(i==arr[ind]&&isEq),(i==1)); tot%=m; } return dp[isEq][was1][ind]=tot; } ll mexp(ll a, ll b){ if (b==0){ return 1; } ll ans = mexp(a,b/2); ans = (ans*ans)%m; if (b%2==0){ return ans; } else { return (ans*a)%m; } } ll minv(ll x){ return mexp(x,m-2); } int main(){ ll q; cin>>n>>q; string s; cin>>s; for (ll i = 0; i<n; i++){ arr[i]=s[i]-'0'; } for (ll a = 0; a<2; a++){ for (ll b = 0; b<2; b++){ for (ll c = 0; c<n; c++){ dp[a][b][c]=-1; } } } cout<<f(0,true,false)<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...