Editorial-CK1601

editorial
,
1

Lets take A sample string as S = abcd"(2^n - 1) are:

  • a", b", c", d"
  • ab", ac", ad", bc", bd", cd"
  • abc", abd", bcd", acd"
  • abcd"

Our task is to add them all.

If you look carefully, the weighted sum above has a pattern, and with a slight inspection and observation, you get this:

a*((2^0)(11^3)+b((2^1)(11^2))+c((2^2)(11^3))+d((2^3)*(11^0))

Now you can generalise this pattern for an string, which can lead to following code-


#define M 1000000007
 
using namespace std;
code-
long long fast_power(long long a, long long b)
{
     long long res = 1;
     while ( b > 0 ) {
           if ( b&1 ) res = (res*a)%M;
           a = (a*a)%M;
           b = b/2;
     }
     return res;
}
 
int main()
{
    long long sum=0,p,q,k;
    string s;
 
    cin >> s;
 
    k = (int)s.size();
 
    for ( int i = 0; i < k; i++ ) {
          p = fast_power(11LL,(long long)i);
          q = fast_power(2LL,(long long)k-i-1);
          p = (p*q)%M;
          p = (p*(s[k-i-1]-48))%M;
          sum = (sum+p)%M;
    }
 
    cout << sum << endl;
 
    return 0;
}