hdu5464Clarke and problem

最新推荐文章于 2018-06-28 00:59:27 发布

_zidaoziyan

最新推荐文章于 2018-06-28 00:59:27 发布

阅读量742

点赞数

分类专栏： dp

本文链接：https://blog.csdn.net/acm_fighting/article/details/48654989

版权

dp 专栏收录该内容

18 篇文章

订阅专栏

问题描述

克拉克是一名人格分裂患者。某一天，克拉克分裂成了一个学生，在做题。 
突然一道难题难到了克拉克，这道题是这样的：  
给你 $n$ 个数，要求选一些数（可以不选），把它们加起来，使得和恰好是 $p$ 的倍数（ $0$ 也是 $p$ 的倍数），求方案数。  
对于 $n$ 很小的时候，克拉克是能轻易找到的。然而对于 $n$ 很大的时候，克拉克没有办法了，所以来求助于你。

输入描述

第一行一个整数 $\le T \le 10)$ ，表示数据的组数。  
每组数据第一行是两个正整数 $\le n, p \le 1000)$ 。  
接下来的一行有 $n$ 个整数 $a_i(|a_i| \le 10^9)$ ，表示第 $i$ 个数。

输出描述

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

输入样例

1
2 3
1 2

输出样例

Hint

有两种方案：什么也不选；全都选。



如果想到用dp,这个题目还是很简单的
一位dp，两层循环,表示前i个数组成和为j的情况有多少种,
还要注意的一点是一个数不能用两次
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int MOD=1e9+7;
ll dp[2000];
int num[2000];
ll vis[2000][1001];

int main(){
    int t;
    int n,p;
    scanf("%d",&t);
    while(t--){
        mem0(dp);
        dp[0]=1;
        mem0(vis);
        scanf("%d%d",&n,&p);
        for(int i=1;i<=n;i++){
             scanf("%d",&num[i]);
            if(num[i]>=0)
                num[i]=num[i]%p;
            else 
                num[i]=p+num[i]%p;
        }
        for(int j=1;j<=n;j++){
            for(int i=0;i<p;i++){
                int x=(num[j]+i)%p;
                if(x<0)
                    x+=p;
                dp[x]=(dp[x]+dp[i])%MOD;
                if(vis[i][j]!=0){
                    dp[x]=(dp[x]-vis[i][j])%MOD;
                    if(dp[x]<0)
                        dp[x]+=MOD;
                }
                vis[x][j]=(vis[x][j]+dp[i]-vis[i][j])%MOD;
                if(vis[x][j]<0)
                    vis[x][j]+=MOD;
            }
        }
        printf("%I64d\n",dp[0]);
    }
    return 0;
}