Advertisement
TheAnshul

Sam and substrings

Jun 9th, 2018
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
  1. /***************************************************************************
  2. * ####### # *
  3. * # # # ###### # # # # #### # # # # # *
  4. * # # # # # # ## # # # # # # # *
  5. * # ###### ##### # # # # # #### ###### # # # *
  6. * # # # # ####### # # # # # # # # # *
  7. * # # # # # # # ## # # # # # # # *
  8. * # # # ###### # # # # #### # # #### ###### *
  9. ***************************************************************************/
  10. #include<bits/stdc++.h>
  11. #define ll long long
  12. #define pb push_back
  13. #define endl '\n'
  14. #define pii pair<ll int,ll int>
  15. #define vi vector<ll int>
  16. #define all(a) (a).begin(),(a).end()
  17. #define F first
  18. #define S second
  19. #define sz(x) (ll int)x.size()
  20. #define hell 1000000007
  21. #define rep(i,a,b) for(ll int i=a;i<b;i++)
  22. #define lbnd lower_bound
  23. #define ubnd upper_bound
  24. #define bs binary_search
  25. #define mp make_pair
  26. using namespace std;
  27.  
  28. #define N 100005
  29. ll expo(ll base, ll exponent, ll mod) { //return base^exponent modulo modulus
  30. ll ans = 1;
  31. while(exponent !=0 ) {
  32. if((exponent&1) == 1) {
  33. ans = ans*base ;
  34. ans = ans%mod;
  35. }
  36. base = base*base;
  37. base %= mod;
  38. exponent>>= 1;
  39. }
  40. return ans%mod;
  41. }
  42. ll gcd(ll a, ll b) { //return gcd of a,b
  43. if (a == 0) return b;
  44. return gcd(b%a, a);
  45. }
  46. ll modInv(ll a, ll m) { //return modulo inverse of a w.r.t. m
  47. ll gc=gcd(a,m);
  48. a/=gc;m/=gc;
  49. ll m0=m,y=0,x=1;
  50. if (m == 1) return 0;
  51. while (a > 1) {
  52. ll q=a/m,t=m;
  53. m = a % m, a = t;
  54. t = y;
  55. y = x - q * y;
  56. x = t;
  57. }
  58. if (x < 0) x += m0;
  59. return x;
  60. }
  61. int main()
  62. {
  63. ios_base::sync_with_stdio(false);
  64. cin.tie(0);
  65. cout.tie(0);
  66. int TESTS=1;
  67. // cin>>TESTS;
  68. while(TESTS--)
  69. {
  70. string s;
  71. cin>>s;
  72. ll n=s.length();
  73. ll sum=0;
  74. ll intr;
  75. rep(r,0,n)
  76. {
  77. intr=(s[n-1-r]-'0');
  78. intr=(intr*(n-r))%hell;
  79. intr=(intr*(expo(10,r+1,hell) - 1))%hell;
  80. sum+=intr;
  81. sum=sum%hell;
  82. }
  83. sum=(sum*modInv(9,hell))%hell;
  84. cout<<sum%hell;
  85. }
  86. return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement