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;
}`