【解決方法】再帰的解法を動的計画法(3D-DP)に変換する方法

プログラミングQA

2024.01.16

昨日、こんなものを見つけました質問コンテストで:

問題文：

「0」から「N – 1」までの番号が付けられた「N」個の整数の配列「A」と単一の整数「K」が与えられます。長さが「1」より大きく、連続する要素の合計が「K」で割り切れるサブシーケンスの数を決定する必要があります。

サブシーケンスは、残りの要素の順序を変更せずに要素の一部を削除することによって、元の配列から派生できる配列です。

あなたのタスクは、長さが「1」より大きい部分列の数と、「K」で割り切れる連続する要素の合計を伝えることです。答えは非常に大きい可能性があるため、「10^9 + 7」を法として返します。

制約:
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'K' <= 10^9
1 <= 'A[i]' <= 10^9
制限時間：1秒

私が試したこと:

私のコード:

int mod = 1e9+7;
long long solve(vector <int> &a,int k,int i,int l,int last){
    if(i==0){
        if(l>1) return 1;
        else return 0;
    }
    else{
        if(last==-1 || ((a[last-1]+a[i-1])%k==0)){
            return(solve(a,k,i-1,l+1,i)%mod + solve(a,k,i-1,l,last)%mod)%mod;
        }else{
            return solve(a,k,i-1,l,last)%mod;
        }
    }
}
long long kDivsibleSubsequences(int n, int k, vector <int> &a){
    return solve(a,k,n,0,-1)%mod;
}