以下の動的計画法を考えます。

\(\text{dp}[i][j] =( i\) 日目まで移動して都市 \(j\) にいる時のスコアの合計の最大値 \()\)

このとき、\(\text{dp}[K][1],\text{dp}[K][2],\ldots,\text{dp}[K][N]\) の最大値 がこの問題の答えとなります。

また、\(\text{dp}[1][i]=P_i \bmod Q\) と初期化します。

遷移については、\(M\) 本のルートについて、\(\text{dp}[j+1][b_k]\leftarrow \max (\text{dp}[j+1][b_k],\text{dp}[j][a_k]+((P_{b_k}\times (j+1)) \bmod Q))\) と更新すればよいです。

これで、ありうる滞在計画のうちの最大のスコアが求められます。

時間計算量は \(\mathrm{O}((N+M)K)\) となります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    vector<int> p(n);
    for (auto& e : p) cin >> e;
    vector<pair<int, int>> ab;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        ab.emplace_back(a, b);
    }
    vector<int> dp(n, 0);
    for (int i = 0; i < n; ++i) dp[i] = p[i] % q;
    for (int d = 2; d <= k; ++d) {
        vector<int> ndp(n, -1e9);
        for (auto [a, b] : ab) {
            ndp[b] = max<int>(ndp[b], dp[a] + ((long long)p[b] * d) % q);
        }
        dp = move(ndp);
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}