D

二分 贪心

删掉个元素，剩下每个连续段，元素求和，取为答案，问答案最大值？

首先这个最大化最小值就是在暗示二分，然后里，是要我们把这个序列拆成多段，约束是要删掉个来实现拆分。

这个的思路也比较显然，拆分数组，每一段需要满足一定限制才能拆出来，约束是拆的次数，那么一般就贪心的拆，然后看操作次数能否满足约束。具体来说就是我们二分出来最小值，那么每一段元素和不小于这个最小值了，就可以拆出来。然后有一个贪心是，如果拆出来段数大于要求，肯定也是可以的，因为我们可以把两段合并，减小段数到，而合并了元素和只会变大（元素全是正数），肯定依然满足不小于最小值的约束，所以贪心地能拆就拆。

然后一个观察是，开头和结尾一定是删掉的，这样能使得使用地操作次数尽可能大。当然这个观察不出来其实也可做，枚举开头和结尾删不删，取即可

需要特判

void solve(){
	int n,k;
	cin>>n>>k;
	
	vi a(n+1);
	int sum=0;
	rep(i,1,n){
		cin>>a[i];
		sum+=a[i];
	}
	if(k==0){
		cout<<sum<<'\n';
	}
	else if(k==1){
		cout<<sum-min(a[1],a[n])<<'\n';
	}
	else{
		int l=0,r=sum;
		auto check=[&](int x)->bool{
			int cnt=0,sum=0;
			rep(i,2,n-1){
				sum+=a[i];
				if(sum>=x){
					sum=0;
					cnt++;
					i++;
				}
			}	
			return cnt>=k-1;
		};
		while(l<=r){
			int m=(l+r)/2;
			if(check(m))l=m+1;
			else r=m-1;
		}
		cout<<r<<'\n';
	}
}

E

数论

当前元素为，付出代价，可以变成，这么看有点抽象，实际上也等价于付出代价，变成。问操作次，恰好变成的最小代价。

手玩可以发现，每次，就能在仅付出的代价，就变成接近的数字，但如果想直接变成则需要付出代价，显然想让代价小，应该采取每次乘上一个小数的倍增做法。实际上更进一步，就是每次乘上的一个因子是最优的。

那么最多操作次就能得到，可以考虑，表示操作次，得到的最小代价，对于，可以转移到所有倍数，这是个调和级数枚举，上界是询问的上界，可以接受。预处理，询问直接查表

最后的问题是可能很大，但根据我们的结论，得到只需要次，实际上更多的操作都是无意义的，在转移时大于左右的更大的，都等于。所回答前，先对，是我们选区的一个阈值，精确的讲，就够了

const int  K = 19;
int dp[K][N];
void init()
{
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i < N; i++) {
        dp[1][i] = i - 1;
    }
    for (int k = 2; k < K; k++) {
        for (int i = 2; i < N; i++) {
            dp[k][1] = 0;
            for (int j = 1; i * j < N; j++) {
                dp[k][i * j] = min(dp[k][i * j], dp[k - 1][i] + j - 1);
            }
        }
    }
}

void solve(){
	int n,m;
	cin>>n>>m;
	n=min(n,K-1);
	cout<<dp[n][m]<<'\n';
}

F

状态机 矩阵快速幂优化

一个串，重复次，问不减的非空子序列个数。

很大，显然要么可以推式子，要么就是矩阵快速幂优化。

先考虑不重复怎么，就是子序列，每一个，考虑他能接在多少个之前选的子序列后面，能不能接还要看之前选的子序列，最后一个元素是，所以需要两个状态区分，表示考虑前个元素，结尾为的子序列个数，可以滚动掉。

转移就是，首先当前元素可以不选，首先可以继承上一轮的方案数。然后如果当前,可以接在之前的结尾的后面，还可以自己新开一个子序列。当前类似，可以接在之前的后面，也可以自己单开一个子序列

这里的重复次是对于整个串来说的，我们想矩阵快速幂，就必须得到整个串对应的转移矩阵。由上面的分析我们可以得到遇到一个的转移矩阵，那么整个串的矩阵就是按顺序，把每个元素的矩阵乘起来。注意这里的转移还有加上一个常数，所以状态向量里也得有个，也就是

注意左乘右乘的区别，我们这里让转移矩阵左乘状态向量，那么每个元素的矩阵叠加时，都需要左乘。

typedef vector<vector<long long>> Matrix;

// 矩阵乘法
Matrix multiply(const Matrix &A, const Matrix &B,long long MOD) {
    int n = A.size();
    int m = B[0].size();
    int k = B.size();
    Matrix C(n, vector<long long>(m, 0));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int l = 0; l < k; ++l) {
                C[i][j] = (C[i][j] + A[i][l] * B[l][j] % MOD) % MOD;
            }
        }
    }
    return C;
}

// 矩阵快速幂
Matrix power(Matrix A, long long p,long long MOD) {
    int n = A.size();
    Matrix result(n, vector<long long>(n, 0));
    
    // 初始化结果矩阵为单位矩阵
    for (int i = 0; i < n; ++i) {
        result[i][i] = 1;
    }
    
    while (p) {
        if (p % 2 == 1) {
            result = multiply(result, A,MOD);
        }
        A = multiply(A, A,MOD);
        p /= 2;
    }
    
    return result;
}
//c=0 nf[0]=2f[0]+1 nf[1]=f[1]
//c=1 nf[0]=f[0] nf[1]=2f[1]+1+f[0]
//状态 (f[0],f[1],1)
void solve(){
	int n;
	string s;
	cin>>n>>s;
	
	Matrix f={
		{1,0,0},
		{0,1,0},
		{0,0,1}
	};
	
	Matrix f0={
		{2,0,1},
		{0,1,0},
		{0,0,1}
	};
	
	Matrix f1={
		{1,0,0},
		{1,2,1},
		{0,0,1}
	};
	
	Matrix start={
		{0},
		{0},
		{1}
	};
	for(char c:s){
		if(c=='0'){
			f=multiply(f0,f,M1);
		}
		else{
			f=multiply(f1,f,M1);
		}
	}
	
	f=power(f,n,M1);
	Matrix ans=multiply(f,start,M1);
	cout<<(ans[0][0]+ans[1][0])%M1<<'\n';
}