題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5464

解題思路：

由于p很小，而ai很大，所以先把ai%p，由于ai可能有負數，所以ai=(ai%p+p)%p

接下來就是在[0,p-1]這個范圍內去找數了。

dp[i][j]表示前i個數中，取得的數是p的倍數的方案數。狀態轉移就很簡單了，直接上代碼

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 1005; const int mod = 1e9+7; int n,p; int a[maxn],dp[maxn][maxn];int main() {int t;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%d%d",&n,&p);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);a[i] = (a[i] % p + p) % p;}dp[0][0] = 1;for(int i = 1; i <= n; i++)for(int j = 0; j < p; j++)dp[i][j] = (dp[i-1][j] + dp[i-1][(p+j-a[i])%p]) % mod;printf("%d\n",dp[n][0]);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 5464(简单dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。