1630/2023: [Usaco2005 Nov]Ant Counting 数蚂蚁

2023: [Usaco2005 Nov]Ant Counting 数蚂蚁

Time Limit: 4 Sec  Memory Limit: 64 MB

Submit: 85  Solved: 40

[Submit][Status][Discuss]

Description

    有一天,贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物.很快贝茜发现有些蚂蚁长得几乎一模一样,于是她认为那些蚂蚁是兄弟,也就是说它们是同一个家族里的成员.她也发现整个蚂蚁群里有时只有一只出来觅食,有时是几只,有时干脆整个蚁群一起出来.这样一来,蚂蚁们出行觅食时的组队方案就有很多种.作为一头有数学头脑的奶牛,贝茜注意到整个蚂蚁群由T(1≤T≤1000)个家族组成,她将这些家族按1到T依次编号.编号为i的家族里有Ni(1≤Ni≤100)只蚂蚁.同一个家族里的蚂蚁可以认为是完全相同的.

    如果一共有S,S+1….,B(1≤S≤B≤A)只蚂蚁一起出去觅食,它们一共能组成多少种不同的队伍呢?注意:只要两支队伍中所包含某个家族的蚂蚁数不同,我们就认为这两支队伍不同.由于贝茜无法分辨出同一家族的蚂蚁,所以当两支队伍中所包含的所有家族的蚂蚁数都相同时,即使有某个家族换了几只蚂蚁出来,贝茜也会因为看不出不同而把它们认为是同一支队伍.    比如说,有个由3个家族组成的蚂蚁群里一共有5只蚂蚁,它们所属的家族分别为1,1,2,2,3.于是出去觅食时它们有以下几种组队方案:

  ·1只蚂蚁出去有三种组合:(1)(2)(3)

  ·2只蚂蚁出去有五种组合:(1,1)(1,2)(1,3)(2,2)(2,3)

  ·3只蚂蚁出去有五种组合:(1,1,2)(1,1,3)(1,2,2)(1,2,3)(2,2,3)

  ·4只蚂蚁出去有三种组合:(1,2,2,3)(1,1,2,2)(1,1,2,3)

  ·5只蚂蚁出去有一种组合:(1,1,2,2,3)

    你的任务就是根据给出的数据,计算蚂蚁们组队方案的总数.

Input

    第1行:4个用空格隔开的整数T,A,S,B.

    第2到A+1行:每行是一个正整数,为某只蚂蚁所在的家族的编号.

Output

    输出一个整数,表示当S到B(包括S和B)只蚂蚁出去觅食时,不同的组队方案数.

    注意:组合是无序的,也就是说组合1,2和组合2,1是同一种组队方式.最后的答案可能很大,你只需要输出答案的最后6位数字.注意不要输出前导0以及多余的空格.

Sample Input

3 5 2 3 1 2 2 1 3

Sample Output

10 样例说明 2只蚂蚁外出有5种组合,3只蚂蚁外出有5种组合.共有10种组合

HINT

Source

Silver

题解:首先显然是个DP,而且是个经典题,以蚂蚁数和最靠后的家族数为转移即可,可是这样子问题来了——这样子的数据规模(1000家族×100只蚂蚁=100000只,再加上×1000家族,这样子非得MLE不可),于是又被雷到了,直到看到了hzwer神犇的博客(OTLhzwer,传送门),发现实际上数组神马的可以滚动存储,而至于最后求某一段的和只需要弄个前缀和数组即可。。。OTLorz,感觉自己渣渣哒

(还有BZOJ双倍经验果断好评如潮!!!^_^)

 1 /**************************************************************
 2     Problem: 2023
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:184 ms
 7     Memory:2588 kb
 8 ****************************************************************/
 9  
10 {/**************************************************************
11     Problem: 1630
12     User: HansBug
13     Language: Pascal
14     Result: Accepted
15     Time:184 ms
16     Memory:2588 kb
17 ****************************************************************/}
18   
19 const p=1000000;
20 var
21    i,j,k,l,m,n,r:longint;
22    a:array[0..2000] of longint;
23    b,c:array[0..2,0..100500] of longint;
24 begin
25      readln(n,m,l,r);
26      fillchar(a,sizeof(a),0);
27      for i:=1 to m do
28          begin
29               readln(j);
30               inc(a[j]);
31          end;
32      b[0,0]:=1;
33      for i:=0 to m do c[0,i]:=1;
34      for i:=1 to n do
35          for j:=0 to m do
36              begin
37                   inc(b[i mod 2,j],c[(i-1) mod 2,j]);
38                   if (j-a[i]-1)>=0 then dec(b[i mod 2,j],c[(i-1) mod 2,j-a[i]-1]);
39                   b[i mod 2,j]:=b[i mod 2,j] mod p;
40                   if j<>0 then
41                      c[i mod 2,j]:=(c[i mod 2,j-1]+b[i mod 2,j]) mod p
42                   else
43                       c[i mod 2,j]:=b[i mod 2,j] mod p;
44                   b[(i-1) mod 2,j]:=0;
45              end;
46      writeln(((c[n mod 2,r]-c[n mod 2,l-1]) mod p+p) mod p);
47      readln;
48 end.     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏写代码的海盗

来自朝鲜的问候 golang入坑系列

鸿渐于陆 本想着写满十八式,但按照目前的进度来看,是很难凑够十八式了。所以还是那句话,量力而行,适可而止。能写多少就写多少,我没法保证看完这本golang脱口秀...

3255
来自专栏程序人生 阅读快乐

《算法Ⅰ~Ⅳ(C++实现)——基础、数据结构、排序和搜索 (第三版)》

本书通过C++实现方案以简洁、直接的方式对书中的算法和数据结构进行表述,并向学生提供在实际应用中验证这种方法的手段。

1012
来自专栏java达人

或许,这会是全民皆知的一门编程语言

不久前,国务院印发了《新一代人工智能发展规划》,其中明确指出,要实施全民智能教育项目,在中小学阶段设置人工智能相关课程,逐步推广编程教育,鼓励社会力量参与寓教于...

2078
来自专栏数据结构与算法

1009. 分配任务

1009. 分配任务 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 在社会实践活动中有三项...

2274
来自专栏海天一树

我是如何成为一名少儿编程竞赛老师的

2017年9月,我以前一个同事问我能不能教他小孩Theo学习编程,因为以前在同一家公司时,我那同事经常带Theo去公司,我和Theo也认识,所以我答应了。

1904
来自专栏专知

【LeetCode 344】关关的刷题日记26 Reverse String

关关的刷题日记26 – Leetcode 344. Reverse String 题目 Write a function that takes a string...

2757
来自专栏大数据文摘

奇怪的数字0.577不断出现在我们身边

1422
来自专栏北京马哥教育

7个案例15分钟让你了解Python套路!

古人云:书山有路勤为径 学海无涯苦作舟 。 注:一般标榜着 “ XX天学会XX”、“ XX 分钟了解XX”的文章都不会是让你增长功力的文章,如本文。 随着互联...

3706
来自专栏企鹅号快讯

或许,这会是全民皆知的一门编程语言

不久前,国务院印发了《新一代人工智能发展规划》,其中明确指出,要实施全民智能教育项目,在中小学阶段设置人工智能相关课程,逐步推广编程教育,鼓励社会力量参与寓教于...

3665
来自专栏专知

关关的刷题日记11——Leetcode 1. Two Sum 方法2、3

关小刷刷题11 – Leetcode 1. Two Sum 方法2、3 方法2 方法2:先将数组进行排序,设置两个左右指针,若sum>target, 那么右指针...

3517

扫码关注云+社区

领取腾讯云代金券