• 【codechef】January Challenge 2015

    【codechef】January Challenge 2015

    CHEFSTON[crayon-5a2e850722b09782370920/]GCDQgcd满足区间加法TAT,所以维护前缀和后缀和就好了[crayon-5a2e850722b1b706109695/]SEAVOTE去掉所有0后若∑bi<tot或∑bi>=100+n则无解否则有解[crayon-5a2e850722b24671253419/]ONEKING按照右端点排序,选择第一个的右端点,删去覆盖其的线段。。。剩下的线段同理[crayon-5a2e850722b2b803915679/]CLPERM答案根据第一个不能合成的数奇偶性得...

  • 【bzoj1042】[HAOI2008]硬币购物

    【bzoj1042】[HAOI2008]硬币购物

    Description硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。Input第一行c1,c2,c3,c4,tot下面tot行d1,d2,d3,d4,sOutput每次的方法数SampleInput1251023231101000222900SampleOutput427HINT数据规模di,s<=100000tot<=1000题解我想起了cf的某道题。。。dp预处理+容斥原理byvoid:设F[i]为不考虑每种硬币的数量限制的...

    12014年11月30日4,721递推与动规,容斥原理
  • 【cf451E】Devu and Flowers

    【cf451E】Devu and Flowers

    Devuwantstodecoratehisgardenwithflowers.Hehaspurchased n boxes,wherethe i-thboxcontains fi flowers.Allflowersinasingleboxareofthesamecolor(hencetheyareindistinguishable).Also,notwoboxeshaveflowersofthesamecolor.NowDevuwantstoselect exactly s flowersfromtheboxestodecoratehisgarden.Devuwouldliketoknow,inhowmanydifferentwayscanheselecttheflowersfromeachbox?Sincethisnumbermaybeverylarg...

    02014年7月25日3,231排列组合,乘法逆元,容斥原理
  • 【bzoj1853】[Scoi2010]幸运数字

    【bzoj1853】[Scoi2010]幸运数字

    Description在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“幸运号码”总是太少了,比如在[1,100]的区间内就只有6个(6,8,66,68,86,88),于是他又定义了一种“近似幸运号码”。lxhgww规定,凡是“幸运号码”的倍数都是“近似幸运号码”,当然,任何的“幸运号码”也都是“近似幸运号码”,比...

    02014年4月27日2,797容斥原理
  • 【bzoj2393】Cirno的完美算数教室

    【bzoj2393】Cirno的完美算数教室

    Description~Cirno发现了一种baka数,这种数呢~只含有2和⑨两种数字~~现在Cirno想知道~一个区间中~~有多少个数能被baka数整除~但是Cirno这么天才的妖精才不屑去数啦只能依靠聪明的你咯。Input一行正整数LR(1<L<R<10^10)Output一个正整数,代表所求的答案SampleInput1100SampleOutput58HINT此题数据范围应该是10^910^9中只含2和9的数,且不被其它这样的数整除的baka数只有30个左右于是我们可以利用容斥原...

    42014年4月26日2,819容斥原理