动态规划_ 选出一些数相加，问最后是m的倍数的方案有多少种

系统管理员 2022-08-08 17:59 38阅读 0赞

**题意：给定n个数，让你判断是否能从中选出一些数相加，使得他们的和能够整除m；**

**分析：这类dp状态转移感觉比较好想，可以从第一项开始每次都把他的结果记录下来，然后轮到后面某一项的时候，直接利用前面的结果进行状态转移。注意记录结果的时候不能直接更新dp数组，因为这样会导致这一项被重复利用。可以享用数组保存下来，后来在更新。**

[http://codeforces.com/contest/577/problem/B][http_codeforces.com_contest_577_problem_B]

B. Modulo Sum

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a sequence of numbers *a*1, *a*2, ..., *a**n*, and a number*m*.

Check if it is possible to choose a non-empty subsequence *a**i**j* such that the sum of numbers in this subsequence is divisible by*m*.

Input

The first line contains two numbers, *n* and*m* (1 ≤ *n* ≤ 106,2 ≤ *m* ≤ 103) — the size of the original sequence and the number such that sum should be divisible by it.

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 109).

Output

In the single line print either "YES" (without the quotes) if there exists the sought subsequence, or "NO" (without the quotes), if such subsequence doesn't exist.

Sample test(s)

Input

3 5
    1 2 3

Output

YES

Input

1 6
    5

Output

Input

4 6
    3 1 1 3

Output

YES

Input

6 6
    5 5 5 5 5 5

Output

YES

Note

In the first sample test you can choose numbers 2 and3, the sum of which is divisible by 5.

In the second sample test the single non-empty subsequence of numbers is a single number5. Number 5 is not divisible by6, that is, the sought subsequence doesn't exist.

In the third sample test you need to choose two numbers  3 on the ends.

In the fourth sample test you can take the whole subsequence.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=1000010;
    
    int a[N];
    int dp[N];
    int v[N];
    int main()
    {
        int n=in(),mod=in();
        for(int i=0;i<n;i++)
        {
            a[i]=in()%mod;
        }
    
        for(int i=0;i<n && !dp[0];i++)
        {
            int cnt=0;
            for(int j=0;j<mod && !dp[0];j++)
            {
                if(dp[j])
                {
                    v[cnt++]=((j+a[i])%mod);//不能直接更新dp数组，先把结果记录下来
                }
            }
            for(int j=0;j<cnt;j++)
            {
                dp[v[j]]=1;
            }
            dp[a[i]]=1;
        }
        puts(dp[0]?"YES" : "NO");
        return 0;
    }

# Clarke and problem #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)**  
**Total Submission(s): 653    Accepted Submission(s): 272**

Problem Description

Clarke is a patient with multiple personality disorder. One day, Clarke turned into a student and read a book.  
Suddenly, a difficult problem appears:  
You are given a sequence of number  *a*1,*a*2,...,*a**n* and a number  *p*. Count the number of the way to choose some of number(choose none of them is also a solution) from the sequence that sum of the numbers is a multiple of  *p*(  0 is also count as a multiple of  *p*). Since the answer is very large, you only need to output the answer modulo  109\+7

Input

The first line contains one integer  *T*(1≤*T*≤10) \- the number of test cases.  
 *T* test cases follow.  
The first line contains two positive integers  *n*,*p*(1≤*n*,*p*≤1000)  
The second line contains  *n* integers  *a*1,*a*2,...*a**n*(|*a**i*|≤109).

Output

For each testcase print a integer, the answer.

Sample Input

1
    2 3
    1 2

Sample Output

2
    
    Hint:
    2 choice: choose none and choose all.

Source

[BestCoder Round \#56 (div.2)][BestCoder Round _56 _div.2]  
  
[http://acm.hdu.edu.cn/showproblem.php?pid=5464][http_acm.hdu.edu.cn_showproblem.php_pid_5464]

**题意：给定n个数，存在负数，让你求出重中选出一些数能够整除m的方案数。  
分析：数据中有负数，直接模m再加上m就能变成正数。然后记录结果，逐项递推。**

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<ll ,ll > pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=100010;
    
    int a[1001];
    ll dp[1111];
    pii v[1111];
    
    const int mod=1e9+7;
    int main()
    {
        int T=in();
        while(T--)
        {
            int n=in(),p=in();
    
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
                if(a[i]<0) a[i]=a[i]%p+p;
                else a[i]%=p;
            }
            int cnt;
            mem(dp,0);
            dp[0]=1;
            for(int i=0;i<n;i++)
            {
                cnt=0;
                for(int j=0;j<p;j++)
                {
                    if(dp[j])
                    {
                        ll tmp=(a[i]+j)%p;
                        v[cnt++]=pii(tmp,dp[j]);
                    }
                }
                for(int j=0;j<cnt;j++)
                {
                    dp[v[j].first]=(dp[v[j].first]+v[j].second)%mod;
                    //if(dp[v[j].first]>=mod) dp[v[j].first]-=mod;
                }
    
            }
    
            printf("%d\n",dp[0]);
        }
        return 0;
    }

# Happy Matt Friends #

**Time Limit: 6000/6000 MS (Java/Others)    Memory Limit: 510000/510000 K (Java/Others)  
Total Submission(s): 1380    Accepted Submission(s): 547**

Problem Description

Matt has N friends. They are playing a game together.  
  
Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins.  
  
Matt wants to know the number of ways to win.

Input

The first line contains only one integer T , which indicates the number of test cases.  
  
For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 10 6 ).  
  
In the second line, there are N integers ki (0 ≤ k i  ≤ 10 6 ), indicating the i-th friend’s magic number.

Output

For each test case, output a single line “Case \#x: y”, where x is the case number (starting from 1) and y indicates the number of ways where Matt can win.

Sample Input

2 3 2 1 2 3 3 3 1 2 3

Sample Output

Case #1: 4 Case #2: 2 
        
         Hint In the ﬁrst sample, Matt can win by selecting: friend with number 1 and friend with number 2. The xor sum is 3. friend with number 1 and friend with number 3. The xor sum is 2. friend with number 2. The xor sum is 2. friend with number 3. The xor sum is 3. Hence, the answer is 4.

Source

[2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交）][2014ACM_ICPC_-]

[http://acm.hdu.edu.cn/showproblem.php?pid=5119][http_acm.hdu.edu.cn_showproblem.php_pid_5119]

**题意：给定n个数，求从中选出一些数，求选出的数中小于m的方案数。**

**分析：这题跟前面两题差不多，也是从每一项开始递推，记录结果，然后更新dp数组。**

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=1111111;
    
    int dp[N];
    pii v[N];
    int a[44];
    
    
    int main()
    {
        int T=in();
        int ii=1;
        while(T--)
        {
            int n=in(),m=in();
            for(int i=1;i<=n;i++)
            {
                a[i]=in();
            }
            mem(dp,0);
            
            dp[0]=1;
            int cnt=0,tmp;
    
            for(int i=1;i<=n;i++)
            {
                cnt=0;
                for(int j=0;j<N;j++)
                {
                    if(dp[j]) v[cnt++]=pii(j^a[i],dp[j]);
                }
                for(int j=0;j<cnt;j++)
                {
                    dp[v[j].first]+=v[j].second;
                }
            }
            ll ans=0;
            for(int i=m;i<N;i++)
            {
                ans+=dp[i];
            }
            printf("Case #%d: %I64d\n",ii++,ans);
    
        }
        return 0;
    }

[http_codeforces.com_contest_577_problem_B]: http://codeforces.com/contest/577/problem/B
[BestCoder Round _56 _div.2]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2356+%28div.2%29&source=1&searchmode=source
[http_acm.hdu.edu.cn_showproblem.php_pid_5464]: http://acm.hdu.edu.cn/showproblem.php?pid=5464
[2014ACM_ICPC_-]: http://acm.hdu.edu.cn/search.php?field=problem&key=2014ACM%2FICPC%D1%C7%D6%DE%C7%F8%B1%B1%BE%A9%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B1%B1%CA%A6%BA%CD%C9%CF%BD%BB%A3%A9&source=1&searchmode=source
[http_acm.hdu.edu.cn_showproblem.php_pid_5119]: http://acm.hdu.edu.cn/showproblem.php?pid=5119