《牛客》-E小红的好数组

本文主要是介绍《牛客》-E小红的好数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路: 找规律 + 组合数学

case给的非常良心

可以分类讨论，大概有4种类似的序列

arr1 = [偶数，偶数，偶数，偶数，偶数，偶数， ...]

arr2 = [奇数，奇数，偶数，奇数，奇数，偶数，...]

arr3 = [奇数，偶数，奇数，奇数，偶数，奇数，...]

arr4 = [偶数，奇数，奇数，偶数，奇数，奇数，...]

奇数/偶数的分布，呈现强烈的规律

最终为这4种情况的组合方案和

Accode:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
int n,k;
int q_pow(int a,int b,int p) {int res=1;while(b) {if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;
}
void solve() {cin>>n>>k;int k2=k/2,k1=k-k2;int a1=q_pow(k2,n,MOD);int a2=q_pow(k2,n/3,MOD)*q_pow(k1,n-n/3,MOD)%MOD;int a3 = q_pow(k2, (n+1)/3,MOD) * q_pow(k1, n - (n+1)/3,MOD) % MOD;int a4 = q_pow(k2, (n+2)/3,MOD) * q_pow(k1, n - (n+2)/3,MOD) % MOD;cout<<(a1+a2+a3+a4)%MOD;
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int tt=1;//cin>>tt;while(tt--)	{solve();}return 0;
}

over~

这篇关于《牛客》-E小红的好数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---