Skip to content

11280: 【原1280】整装待发

题目

题目描述

author: Chen Xutong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1280

Description

无奈可怜的cxt同学发现电话是没有信号的。。。。。(远古时代哪有信号 = =)。于是只能自己去寻找出口了。当然首要问题是。。。。生存。他找遍了周围所有的东西,比如花花草草,比如树枝树杈,比如恐龙遗骸。。。。。。一共有 N 个东西(装备),他给每个东西确定了一个价值,这个价值是个整数Ri,在这危机四伏的地方,cxt不得不迷信一次,他的幸运数字是F,他希望带的装备的价值总和是F的倍数。他现在想知道的是,他有多少种方案来佩戴这些装备。btw,因为cxt不喜欢裸奔,所以不能什么都不带就出门。

Input Format

第一行:两个整数N和F,1 ≤ N ≤ 2000,1 ≤ F ≤ 1000

第二行到N + 1行:第i + 1行有一个整数Ri ,表示第i件装备的价值,1 ≤ Ri ≤ 10^5

Output Format

第一行:单个整数,表示方案数除以10^8的余数

Sample Input

4 5
1
2
8
2

Sample Output

3

Hint

有两种方案都是8 + 2 = 10,只是选的装备不一样,第三种方案是2 + 2 + 1 = 5

yyong119's solution

#include <cstdio>
#include <cstring>
#define MAX_N 2005
#define MAX_F 1005
const int K = (int)1e8;
int N, MOD, num;
int f[MAX_N][MAX_F];
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - 48, ch = getchar();
    return res * flag;
}
int main() {
    N = read(); MOD = read();
    num = read(); num %= MOD; f[0][num] = 1;
    for (register int i = 1; i < N; ++i) {
        num = read();
        num %= MOD;
        for (register int j = 0; j < MOD; ++j) {
            int next = (j + num) % MOD;
            f[i][next] = (f[i - 1][j] + f[i - 1][next]) % K;
        }
        ++f[i][num];
    }
    int ans = 0;
    printf("%d\n", f[N - 1][0] % K);
    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
#define M 100000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, ff, a[2005], f[2005][1005] = {0};
void init(){
    n = read(), ff = read();
    for (int i = 1; i <= n; ++i) 
        a[i] = read();
}
void solve(){
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i){
        a[i] %= ff;
        for (int j = 0, k = a[i]; j < ff; ++j, k = (k == ff - 1 ? 0: k + 1))
            f[i][k] = (f[i - 1][k] + f[i - 1][j]) % M;
    }
    printf("%d\n", (f[n][0] + M - 1) % M);
}
int main(){
    init();
    solve();
    return 0;
}