## Question 2: Quantum Plasma Resonance You are c...

Question

Question 2: Quantum Plasma Resonance

You are configuring a linear sequence of exactly N plasma nodes. Each node must be calibrated to a specific intensity level from 1 to F (inclusive).

Under normal circumstances, the total power output of the sequence is simply the sum of all individual node intensities. However, the sequence requires exactly one Fusion Coil to remain stable. You must install exactly one Fusion Coil between two adjacent plasma nodes.

The coil physically merges the two adjacent nodes, causing their intensities to multiply rather than add. The remaining N − 2 nodes in the sequence continue to add their intensities to the total.

For example, if N = 4 and the coil is placed between node 2 and node 3, the total power becomes:

I1 + (I2 × I3) + I4

The final total power output must equal exactly T.

Find the total number of valid configurations.

A configuration is considered distinct if:

The sequence of N intensities is different, or
The geometric position of the Fusion Coil is different.

Since the answer can be very large, output it modulo 10^9 + 7.

Input Format

The first line contains an integer N, denoting the number of plasma nodes.
The second line contains an integer F, denoting the maximum intensity level of each node.
The third line contains an integer T, denoting the target total power output.

Constraints

3 ≤ N ≤ 1000
1 ≤ F ≤ 50
1 ≤ T ≤ 5000

Example 1

Input

text
3
3
5

Output

Explanation

With 3 nodes and a maximum intensity of 3, there are 2 possible Fusion Coil positions. Each position allows exactly 5 valid intensity assignments whose total power equals 5, giving:

2 × 5 = 10

Example 2

Input

text
4
2
5

Output

Explanation

With 4 nodes and maximum intensity 2, the Fusion Coil can be placed in 3 different positions. Each position yields exactly 5 valid intensity assignments achieving total power 5.

Hence the total number of configurations is:

3 × 5 = 15

Example 3

Input

text
10
1
9

Output

Explanation

Since the maximum intensity is 1, all 10 nodes must have intensity 1. Placing the Fusion Coil at any of the 9 possible adjacent positions gives:

1 + ... + (1 × 1) + ... + 1 = 9

Therefore, there are 9 valid configurations.

C++ code full optimal

Answer 1

Approach

For any fixed Fusion Coil position, let its adjacent node intensities be $a$ and $b$ .

The remaining $K=N-2$ nodes must satisfy:

x_1+x_2+\cdots+x_K = T-ab

where every $x_i\in[1,F]$ .

All $N-1$ coil positions have the same number of assignments, so:

\text{answer}=(N-1)\sum_{a=1}^{F}\sum_{b=1}^{F} \text{ways}[T-ab]

Here, ways[s] is the number of ordered assignments of $N-2$ values from $1$ to $F$ whose sum is $s$ .

We calculate ways using DP. The transition is:

dp_{\text{new}}[s]=\sum_{x=1}^{F}dp[s-x]

A sliding window reduces each DP layer from $O(TF)$ to $O(T)$ .

Complexity

O(NT+F^2)

Memory:

O(T)

cpp
#include <bits/stdc++.h>
using namespace std;

static constexpr long long MOD = 1'000'000'007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, F, T;
    cin >> N >> F >> T;

    const int remainingNodes = N - 2;

    // dp[s] = number of ways for the processed normal nodes
    // to have total intensity exactly s.
    vector<long long> dp(T + 1, 0);
    vector<long long> nextDp(T + 1, 0);

    dp[0] = 1;

    for (int node = 0; node < remainingNodes; ++node) {
        long long windowSum = 0;

        for (int sum = 0; sum <= T; ++sum) {
            // Add dp[sum - 1], corresponding to choosing intensity >= 1.
            if (sum - 1 >= 0) {
                windowSum += dp[sum - 1];
                if (windowSum >= MOD) {
                    windowSum -= MOD;
                }
            }

            // Remove dp[sum - F - 1], which is outside the range
            // dp[sum - 1] + ... + dp[sum - F].
            if (sum - F - 1 >= 0) {
                windowSum -= dp[sum - F - 1];
                if (windowSum < 0) {
                    windowSum += MOD;
                }
            }

            nextDp[sum] = windowSum;
        }

        dp.swap(nextDp);
        fill(nextDp.begin(), nextDp.end(), 0);
    }

    long long configurationsForOnePosition = 0;

    // a and b are ordered because they belong to distinct adjacent nodes.
    for (int a = 1; a <= F; ++a) {
        for (int b = 1; b <= F; ++b) {
            int requiredSum = T - a * b;

            if (requiredSum >= 0 && requiredSum <= T) {
                configurationsForOnePosition += dp[requiredSum];

                if (configurationsForOnePosition >= MOD) {
                    configurationsForOnePosition -= MOD;
                }
            }
        }
    }

    long long answer =
        configurationsForOnePosition * (N - 1LL) % MOD;

    cout << answer << '\n';
    return 0;
}

Why multiplying by $N-1$ is valid

There are exactly $N-1$ adjacent pairs where the coil can be placed. For every fixed position, the two multiplied nodes and the $N-2$ added nodes have the same allowed range, so every position has the same number of valid intensity assignments. Since different coil positions count as different configurations, the fixed-position count is multiplied by $N-1$ .

## Question 2: Quantum Plasma Resonance You are c...

سؤال