P15889 [COCI 2025/2026 #6] 零花钱 / Džeparac

ooliver 发布于 6 小时前 44 次阅读 OI

AI 摘要

零花钱如何分配？一个简单的数学技巧，就能解决看似复杂的发放问题。本文揭示分割整数与2的幂次的神奇关联，带你用“隔板法”一眼看穿零花钱分配的本质，答案比你想象的更简洁。

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<bits/stdc++.h>
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<<qpow(2,n/2);
    return 0;
}