hdu 5464 Clarke and problem dp

2022-09-15 09:56:14

Clarke and problem

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5464

Description

克拉克是一名人格分裂患者。某一天，克拉克分裂成了一个学生，在做题。

突然一道难题难到了克拉克，这道题是这样的：

给你nn个数，要求选一些数（可以不选），把它们加起来，使得和恰好是pp的倍数（00也是pp的倍数），求方案数。

对于nn很小的时候，克拉克是能轻易找到的。然而对于nn很大的时候，克拉克没有办法了，所以来求助于你。

Input

第一行一个整数T(1 \le T \le 10)T(1≤T≤10)，表示数据的组数。

每组数据第一行是两个正整数n, p(1 \le n, p \le 1000)n,p(1≤n,p≤1000)。

接下来的一行有nn个整数a_i(|a_i| \le 10^9)ai(∣ai∣≤109)，表示第ii个数。

Output

对于每组数据，输出一个整数，表示问题的方案数，由于答案很大，所以求出对10^9+710
9
+7的答案即可。

Sample Input

1
2 3
1 2

Sample Output

HINT

题意

题解：

设d(i, j)d(i,j)表示前ii个数，模pp为jj的方案数，则容易得到d(0, 0)=1, d(i, j)=d(i-1, j)+\sum_{j=0}^{p-1} d(i-1, (j-a[i]) \ mod \ p)d(0,0)=1,d(i,j)=d(i−1,j)+∑j=0p−1d(i−1,(j−a[i]) mod p)，很多人没1a是因为没注意|a_i| \le 10^9∣ai∣≤109

代码：

//qscqesze

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <bitset>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 1006

#define mod 1000000007

#define eps 1e-9

#define PI acos(-1)

const double EP  = 1E- ;

int Num;

//const int inf=0x7fffffff;

const ll inf=;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//*************************************************************************************

ll dp[maxn][maxn];

ll p,a[maxn];

int main()

{

    int t;scanf("%d",&t);

    for(int cas=;cas<=t;cas++)

    {

        int n;scanf("%d%I64d",&n,&p);

        for(int i=;i<=n;i++)

            scanf("%I64d",&a[i]);

        for(int i=;i<=n;i++)

        {

            a[i]%=p;

            if(a[i]<)a[i]+=p;

        }

        memset(dp,,sizeof(dp));

        dp[][]=;

        for(int i=;i<=n;i++)

        {

            for(int j=;j<p;j++)

            {

                if(!dp[i-][j])continue;

                dp[i][j]=(dp[i][j]+dp[i-][j])%mod;

                dp[i][(j+a[i])%p] = (dp[i][(j+a[i])%p]+dp[i-][j])%mod;

            }

        }

        printf("%I64d\n",dp[n][]%mod);

    }

}

码农公寓