当前位置：首页 > news >正文

打卡信奥刷题（3026）用C++实现信奥题 P6394 樱花，还有你

news 2026/7/11 22:52:18

P6394 樱花，还有你

题目背景

Dear Ling,
呐，你知道吗？听说樱花飘落的速度是秒速五厘米哦。
……所以，再等等吧！三月，武汉大学，樱花就快来了呢。
你一定会陪我一起看吧，在酥软的阳光下，我会悄悄牵起你的手，感受你熟悉的温度，糟糕，脸儿也不小心被粉嫩嫩的樱花映红的呢。
对了，一定记得带口罩！你那时还是有些虚弱吧。但天依会保护你的！
还有啊，樱花还可以做好多好多的点心呢！收集一些飘落樱花吧，我想喝樱花茶，还想吃樱饼，你一定要亲手给我做嗷！

题目描述

与题意有关的句子已加粗。

但别急，我们就这样彳亍而行吧，需不着停留或回头，前面不是还有kkk棵樱花树么？我算了算，你可要收集恰好nnn朵樱花。我还发现，在第iii棵树下最多能收集到sis_isi朵樱花（收集了000朵樱花也算收集了樱花）。

呐，考考你吧！你有多少种方案能够收集到恰好nnn朵樱花呢？

特殊地，如果你收集不到nnn朵樱花，请告诉我impossible。

注意：如果你早早地收集到了nnn朵樱花，你可以立刻告诉我，也可以陪我继续向前走，一直到第kkk棵樱花树下收集了樱花后就必须交差啦！期间你在任何一棵树收集完樱花后就告诉我，形成的方案都是不同的哦！

输入格式

第一行两个正整数n,kn,kn,k，表示要收集nnn朵樱花，而前方还有kkk棵樱花树。

接下来一行kkk个正整数s1,s2,⋯ ,sks_1,s_2,\cdots,s_ks1,s2,⋯,sk，其中sis_isi表示最多在第iii棵樱花树下收集到sis_isi朵樱花。

输出格式

一行一个整数，表示恰好收集到nnn朵樱花的方案数。

由于答案可能太大，请输出答案对100860011008600110086001取模后的值。

特殊地，如果收集不到nnn朵樱花，请输出一个字符串impossible。

输入输出样例 #1

输入 #1

3 4 1 1 1 1

输出 #1

输入输出样例 #2

输入 #2

10 9 9 6 8 7 9 6 5 4 3

输出 #2

输入输出样例 #3

输入 #3

10 5 2 2 2 2 1

输出 #3

impossible

说明/提示

样例解释 #1

我们以下列方式表示一种方案：(a1,a2,⋯ ,alen)(a_1,a_2,\cdots,a_{len})(a1,a2,⋯,alen)，其中∑i=1lenai=n\sum_{i=1}^{len} a_i =n∑i=1lenai=n，lenlenlen表示在第lenlenlen棵樱花树下收集完樱花后就交差了，aia_iai表示在第iii棵树下收集了aia_iai朵樱花。

那么有下列555种方案：(1,1,1)(1,1,1)(1,1,1)，(1,1,1,0)(1,1,1,0)(1,1,1,0)，(0,1,1,1)(0,1,1,1)(0,1,1,1)，(1,0,1,1)(1,0,1,1)(1,0,1,1)，(1,1,0,1)(1,1,0,1)(1,1,0,1)。

样例解释 #3

最多能收集到999朵樱花，所以不能收集到101010朵樱花，输出impossible。

数据范围

本题采用捆绑测试。

Subtask 1（5 Points），∑si<n\sum s_i < n∑si<n。
Subtask 2（20 Points），n,k≤20n,k \leq 20n,k≤20。
Subtask 3（55 Points），n,k≤5×102n,k \leq 5\times 10^2n,k≤5×102。
Subtask 4（20 Points），n,k≤5×103n,k \leq 5\times 10^3n,k≤5×103。

对于100%100\%100%的数据，1≤n,k≤5×1031 \leq n,k \leq 5\times 10^31≤n,k≤5×103，0≤si≤n0 \leq s_i \leq n0≤si≤n。

题目背景 ( 续 )

何等聪明的你一定会站在某棵树下，捧着nnn朵可爱的樱花，像孩子似的向我邀功吧。
那就别怪我成全你哦，我会轻跳起来，环住你的脖子，揭起你的口罩，尝一尝你的嘴唇。
你会不会说，“像樱花一样甜”呢？
反正，我的脸一定已经像樱花一样红了吧。
……
当你看到这封信，别哭呀……
冬天从这座城市夺走的，春天会补偿我们的。
待你好了，陪我去看樱花，可好？

Yours,
Yi

C++实现

#include<iostream>#include<cstdio>usingnamespacestd;constintM=10086001;intf[5001];longlongs[5001];//前缀和intnum,ans;intmain(){intn,t,i,j,p,k;cin>>n>>k;s[0]=f[0]=1;for(i=1;i<=k;i++){cin>>t;for(j=1;j<=n;j++)//更新前缀和s[j]=s[j-1]+f[j];for(p=n;p>=0;p--)//多重背包f[p]=(f[p]+s[p-1]-s[p-min(t,p)-1])%M;//利用前缀和num+=t;//判断是否有解ans=(ans+f[n])%M;//累加第i棵树下收集n朵花的方案}if(num<n)cout<<"impossible";elsecout<<ans;return0;}