bzoj1630/2023 [Usaco2007 Demo]Ant Counting

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1630

http://www.lydsy.com/JudgeOnline/problem.php?id=2023

【题解】

直接dp，f[i,j]表示第i个种族选了j只蚂蚁的方案数，转移枚举这个种族选择的方案。

然后可以前缀和+滚动数组

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 5e5 + ;

const int mod = 1e6;

# define RG register

# define ST static

int m, n, A, B;

int a[M], bel[M], sum[M];

int f[][], s[][];

int main() {

    cin >> m >> n >> A >> B;

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

        scanf("%d", &bel[i]);

        a[bel[i]] ++;

    }

    int pre = , cur = ;

    f[pre][] = ;

    for (int i=; i<=n; ++i) s[pre][i] = ;

    for (int i=; i<=m; ++i) {

        for (int j=; j<=n; ++j) {

            if(a[i] < j) f[cur][j] = (s[pre][j] - s[pre][j-a[i]-] + mod) % mod;

            else f[cur][j] = s[pre][j];

            if(j == ) s[cur][j] = f[cur][j];

            else s[cur][j] = (s[cur][j-] + f[cur][j]) % mod;

        }

        swap(pre, cur);

    }

    int ans = (s[pre][B] - s[pre][A-] + mod) % mod;

    cout << ans << endl;

    return ;

}

bzoj1630/2023 [Usaco2007 Demo]Ant Counting的相关教程结束。