louisfghbvc的部落格

題目連結:  https://onlinejudge.org/external/106/10616.pdf

題目大意:  找出C n 取 m 整除 d 的數量多少

思路:  動態規劃，記憶化搜索，dp，事實上就是枚舉，並且利用mod將狀態壓縮到剩d，看網上也蠻多打表的方式。這邊提供不太一樣的方法

每個查詢都要重新memo，因為我答案都存在0 0 0，所以每次都要重新。

dp題做熟了，其實都可以先枚舉，再優化。最後變成非遞迴疊代方式。

注意數字可能很大或是負數。

代碼:  

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL arr[205];
LL n, q, d, m;
LL memo[205][25][205];
LL dfs(int c, LL sum, int id){
    if(c == m){
        if(sum) return 0;
        return 1;
    }
    if(id >= n) return 0;
    if(memo[c][sum][id] != -1) return memo[c][sum][id];
    LL res = 0;
    for(int i = id; i < n; ++i){
        res += dfs(c+1, ((sum+arr[i])%d + d)%d, i+1);    
    }
    return memo[c][sum][id] = res;
}

int main()
{
    
    int cas = 1;
    while(cin >> n >> q, n+q){
        for(int i = 0; i < n; ++i) cin >> arr[i];
        printf("SET %d:\n", cas++);
        int qc = 1;
        while(q--){
            memset(memo, -1, sizeof memo);
            cin >> d >> m;
            printf("QUERY %d: %lld\n", qc++, dfs(0, 0, 0));
        }
    }
}