Home About Me

Angry Little N: Thue–Morse Levels and a Polynomial Sum

2026-08-27

Problem background

The task is built around a game with levels numbered from 0 to n − 1. Some levels are ordinary, and the others are bonus levels. The pattern is encoded by a special infinite string s: write a for an ordinary level and b for a bonus level. The levels 0, 1, 2, …, n − 1 form a prefix of s.

The string s is constructed by starting with a single a. Then repeatedly take the current string, swap every a with b and every b with a, and append the swapped copy to the end. This produces

s = abbabaabbaababba…

So level 0 is ordinary, level 1 is a bonus level, level 2 is a bonus level, level 3 is ordinary, and so on. This is the Thue–Morse sequence.

Clearing level i gives f(i) points, where

f(x) = a0 + a1 x + a2 x^2 + … + a_{k-1} x^{k-1}

is a fixed polynomial of degree k − 1. The player clears every bonus level and ignores every ordinary level. The goal is to compute the total score modulo 10^9 + 7.

Input and output

The first line contains a positive integer n, written in binary. The second line contains a positive integer k, the degree of the polynomial plus one. The third line contains k nonnegative integers a0, a1, a2, …, a_{k-1}, the polynomial coefficients.

Output one nonnegative integer: the player's total score modulo 10^9 + 7.

Samples

Sample 1 input:

1000
3
3 2 1

Sample 1 output:

110

The binary input 1000 means n = 8. The score for level i is 3 + 2i + i^2. Levels 1, 2, 4, and 7 are bonus levels. Their scores are 6, 11, 27, and 66, giving 110 in total.

Sample 2 input:

11111100101
4
2 0 2 1

Sample 2 output:

143901603

Sample 3 input:

1001011001101001
16
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

Sample 3 output:

184740992

Constraints

For all test cases:

  • 0 ≤ log2 n < 5 × 10^5
  • 1 ≤ k ≤ 500
  • 0 ≤ ai < 10^9 + 7
  • a_{k-1} ≠ 0

C++ implementation

#include <iostream>
#include <string.h>
using namespace std;
#define RLL register long long
#define LL long long
#define VALUE 1000000007
int n;
int x[512],k;
int getn(LL num){
    return (num)?1+getn(num/10):0;
}
int BtoD(LL num){
    int dec=0,i=0;
    while(num){
        dec+=(num%10)*(1<<i++);
        num/=10;
    }
    return dec;
}
// ordinary exponentiation (mod)
LL normalExponentiation(int base,int power){
    LL res=1;
    for(int i=1;i<=power;i++){
        res*=base;
        res%=VALUE;
    }
    return res%VALUE;
}
// really fast
LL fastExponentiation(LL base,LL power) {
    LL res = 1;
    while (power > 0) {
        if (power & 1) {// equivalent to if(power%2==1)
            res = res * base % VALUE;
        }
        power >>= 1;// equivalent to power=power/2
        base = (base * base) % VALUE;
    }
    return res;
}
LL getScore(int i){
    // level i
    LL res=0,power;
    for(int l=0;l<k;l++){
        power=x[l];
        if(x[l]) res+=fastExponentiation(i,l);// much faster than normalExponentiation
    }
    return res;
}
string mades(string s){
    string news=s;
    for(int i=0;i<n;i++){
        for(int j=0;j<s.size();j++) news+=(s[j]=='a')?\"b\":\"a\";
        s=news;
    }
    return news;
}
int main()
{
    LL num;
    cin>>num>>k;
    n=getn(num);
    for(int i=0;i<k;i++)cin>>x[i];
    string s=mades(\"a\");
    RLL ScoreSum=0;
    int max=BtoD(num);
    for(int i=0;i<max;i++)
        if(s[i]=='b'){
            ScoreSum+=getScore(i);
        }
    cout<<\"SUM:\"<<ScoreSum%VALUE;
    return 0;
}

There is a better way to handle the exponentiation step, but the improved version is not shown here.

Related Posts