Expert.
Put your skills to the test.

Problem summary

Count expressions consisting of operands from 2 through K and binary + or * operators, with no parentheses, whose value is N. Evaluate every operation strictly from left to right. Distinct sequences of symbols count separately.

Constraints

2 < K < N < 80.

Worked example

Official statement sample.

6 3

5

Solution analysis

1. Let ways[v] count expressions evaluating to v. Each single operand d contributes one expression at d. Every additional operand is attached to an existing expression by either +d or *d.
2. Both operations strictly increase the current value because d≥2. Thus process values in increasing order and send ways[v] to v+d and v*d when the destination does not exceed N. A destination may receive contributions from both operations.
3. For N=6,K=3 the five expressions are 2*2+2, 2+2+2, 3+3, 3*2, and 2*3. The expression 2+2*2 evaluates to 8 under the specified rule.

Why it works

Every nontrivial expression has a unique final operator, operand, and prefix expression. The transitions enumerate exactly these decompositions. Increasing value order ensures every prefix has already been counted.

Watch out. Do not use ordinary multiplication precedence. Use exact integer arithmetic: the implementation stores counts as decimal strings, avoiding reliance on an unstated output bound.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
string add(string a,const string&b){
    string result;
    int i=static_cast<int>(a.size())-1;
    int j=static_cast<int>(b.size())-1;
    int carry=0;
    while(i>=0||j>=0||carry){
        int digit=carry;
        if(i>=0){
            digit+=a[i--]-'0';
        }
        if(j>=0){
            digit+=b[j--]-'0';
        }
        result.push_back(char('0'+digit%10));
        carry=digit/10;
    }
    reverse(result.begin(),result.end());
    return result.empty()?"0":result;
}
int main(){
    int n,k;
    cin>>n>>k;
    vector<string>ways(n+1,"0");
    for(int d=2;d<=k;++d){
        ways[d]="1";
    }
    // Every transition goes to a strictly larger value.
    for(int v=2;v<=n;++v){
        for(int d=2;d<=k;++d){
            if(v+d<=n){
                ways[v+d]=add(ways[v+d],ways[v]);
            }
            if(v*d<=n){
                ways[v*d]=add(ways[v*d],ways[v]);
            }
        }
    }
    cout<<ways[n]<<'\n';
}