P15889 [COCI 2025/2026 #6] 零花钱 / Džeparac 考虑枚举每个孩子总共获得的钱数 i， 根据题意知道，可以将 ii 分成几天发放，可以看成把 i 分成若干部分，就变成了在 i−1i-1 个空中放板子，每个空放或不放，共 2i−12^{i-1} 个方案。 再加上每个孩子都不给零花钱的方案，答案就应该是： 1+∑i=1⌊n2⌋2i−1=1+(2⌊n2⌋−1)=2⌊n2⌋\begin{aligned} &1+\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor } 2^{i-1} \ =&1+(2^{\lfloor \frac{n}{2} \rfloor}-1) \ =&2^{\lfloor \frac{n}{2} \rfloor} \end{aligned} 快速幂即可。 代码： C++ #include using namespace std; #define int long long const int mod=1e9+7; int n; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } signed main(){ cin>>n; cout `#include using namespace std; #define int long long const int mod=1e9+7; int n; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } signed main(){ cin>>n; coutqpow(2,n/2); return 0; }`
P15889 [COCI 2025/2026 #6] 零花钱 / Džeparac
笔记