出题人题解 | #Phrase String#

原题解链接：https://ac.nowcoder.com/discuss/150246

显然，当$k\ge vk\backslash ge\; v$时，最优的构造方法为$kk$个$11$ 当时,最优的构造方法为长度为$vv$的序列，两端各有一个$11$,从中间位置开始向左向右各有$\frac{k-2}{2}\backslash frac\{k-2\}\{2\}$个1,也就是$\mathrm{10000...1111...00001}10000...1111...\; 00001$

直接构造输出解的复杂度: $O(k)O(k)$或$O(klogk)O(klogk)$

当然还有更优的做法:即把中间的一段$11$看成等比数列直接算答案,时间复杂度$logklogk$

/*
构造一个长度为v的回文串，至少有k个1 

void make_data(int test) {
	int N = 0, K = 0;
	if(test % 3 == 0) {
		N = 5e4 + test * 2;
		K = N + 2;
	} else if(test % 3 == 1){
		N = 5e4 + test * 2;
		K = N - 2;
	} else {
		N = 5e4 + test * 2;
		K = N - test * 10;
	}
	cout << N << " " << K;
}
*/
#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 1e5 + 10, mod = 1e9 + 7;
int a[MAXN], N, k;
int add(int x, int y) {
	if(x + y < 0) return x + y + mod;
	else return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
	return 1ll * x * y % mod;
}
int fp(int a, int p) {
	int base = 1;
	while(p) {
		if(p & 1) base = mul(base, a);
		a = mul(a, a); p >>= 1;
	}
	return base;
}
signed main() {
	cin >> N >> k;
	int ans = 0;
	if(k >= N) {
		for(int i = 0; i < k; i++) ans = add(ans, fp(2, i));
		cout << ans;
		return 0;
	}
	k -= 2;
	a[0] = a[N - 1] = 1;
	int mid = N / 2;
	for(int i = 1; i <= k / 2; i++) a[mid - i] = 1, a[mid + i - 1] = 1;
	for(int i = 0; i < N; i++) if(a[i]) ans = add(ans, fp(2, i));
	cout << ans;
}