Submission #258648

#TimeUsernameProblemLanguageResultExecution timeMemory
258648dantoh000Lucky Numbers (RMI19_lucky)C++14
0 / 100
367 ms2112 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1000000007; ll mem[100005][2]; int a[100005]; int n,q; ll dp(int id, int lastone){ if (id == 0) return 1; if (mem[id][lastone] != -1) return mem[id][lastone]; ll ret = 0; for (int i = 0; i < 10; i++){ if (lastone && i == 3) continue; ret += dp(id-1,i==1); } ret %= mod; //printf("%d %d %lld\n",id,lastone,ret); return mem[id][lastone] = ret; } ll qu(int l, int r){ ll ret = 0; int ct = 0; for (int i = r; i >= l; i--, ct++){ for (int j = 0; j < a[i]; j++){ ret += dp(ct,j==1); if (ret >= mod) ret -= mod; } } bool isthirteen = 0; for (int i = l+1; i <= r; i++){ if (a[i] == 3 && a[i-1] == 1) isthirteen = true; } if (!isthirteen) ret++; if (ret >= mod) ret -= mod; return ret; } int main(){ scanf("%d%d",&n,&q); for (int i = 0; i < n; i++){ char ch; scanf(" %c",&ch); a[i] = ch-'0'; } memset(mem,-1,sizeof(mem)); printf("%lld\n",qu(0,n-1)); for (int i = 0; i < q; i++){ int t,l,r; scanf("%d%d%d",&t,&l,&r); if (t == 1){ printf("%lld\n",qu(--l,--r)); } else{ a[--l] = r; } } }

Compilation message (stderr)

lucky.cpp: In function 'int main()':
lucky.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
lucky.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&ch);
         ~~~~~^~~~~~~~~~~
lucky.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&t,&l,&r);
         ~~~~~^~~~~~~~~~~~~~~~~~~
#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...