企业官网建设流程全解析

小红开灯（三，hard）

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

（本题和easy版本的唯一区别是，本题小红可以改变任意kk盏灯的状态）
有nn盏灯排成一列，初始为全部都是“开启”状态。

小红每次操作可以改变任意kk盏灯的状态（开启变关闭，关闭变开启），她想知道，进行任意次操作后，可以形成多少种不同的灯的状态？由于答案可能过大，请对109+7109+7取模。

输入描述：

两个正整数n,kn,k，用空格隔开。
1≤k≤n≤1051≤k≤n≤105

输出描述：

一个整数，代表最终状态数对109+7109+7取模的答案。

示例1

输入：

3 2

输出：

4

说明：

可以形成"111"、“100”、“010”、"001"这四种状态。

解题思路

本题是线性空间性质推导的思维题，核心是分析翻转操作生成的状态空间规模。
题目等价于：初始全为开启状态（全1）的长度为n的01灯组，每次可任选恰好k个位置翻转状态，求任意次操作后能得到的不同状态总数。
结合二元线性空间的性质分情况讨论：

1. 当 n == k 时：仅有一种操作（翻转全部灯），只能得到全亮、全灭两种状态，答案固定为2。
2. 当 k < n 时：
   • 若k为奇数：每次翻转奇数个位置，通过多次操作组合可以实现单个位置的独立翻转，因此全部2 n 2^n2n种状态都可达。
   • 若k为偶数：每次翻转偶数个位置，状态中1的个数奇偶性始终与初始状态一致，仅能到达总状态数的一半，总数为2 n − 1 2^{n-1}2n−1。

最终使用快速幂计算对应2的幂次，对10 9 + 7 10^9+7109+7取模即可。算法时间复杂度为O ( log ⁡ n ) O(\log n)O(logn)，极致高效，完全适配n ≤ 10 5 n \le 10^5n≤105的数据约束。

总结

核心逻辑：由k的奇偶性决定翻转操作生成的线性空间维数，直接计算2的对应幂次得到状态总数。
关键操作：分情况判断n与k的大小关系、快速幂计算幂值、模运算处理结果。
效率保障：仅需一次快速幂运算，常数级时间开销，无冗余计算，轻松应对数据上限。

代码简要说明

1. 快速幂实现：powmod函数通过二进制拆分实现模意义下的快速幂，高效计算大指数幂。
2. 冗余代码说明：代码中预计算阶乘、逆元的pre和comb函数为冗余内容，本题并未使用，不影响运行结果。
3. 分情况计算：若n等于k，直接输出2；否则通过k&1判断奇偶性，计算2 n − 1 + ( k & 1 ) 2^{n-1 + (k\&1)}2n−1+(k&1)作为答案，其中奇数指数加1、偶数加0，对应上述结论。
4. 输入输出：使用标准输入输出，配合同步关闭优化读取速度，保证运行效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll maxn=220000;constll inf=1LL<<62;constll MOD=1000000007;ll n,k,ans=0;llpowmod(ll a,ll b){ll res=1LL;for(;b;b>>=1){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;}returnres;}llinv(ll x){returnpowmod(x,MOD-2);}ll f[maxn]={},invf[maxn]={};voidpre(ll n){f[0]=invf[0]=f[1]=invf[1]=1;for(ll i=2;i<=n;i++)f[i]=(f[i-1]*i)%MOD,invf[i]=inv(f[i])%MOD;return;}llcomb(ll n,ll m){if(n<0||m<0||m>n)return0;return((f[n]*invf[n-m])%MOD*invf[m])%MOD;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld",&n,&k);pre(n+5);ans=0;if(n==k)ans=2;elseans=powmod(2,n-1+(k&1));printf("%lld",ans);return0;}