Submission #40389298

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=4e5+10,mod=1e9+7,LIM=4e5;
void add(ll& x,ll y){x=(x+y)%mod;}
void sub(ll& x,ll y){x=(x-y+mod)%mod;}
void tomin(ll& x,ll y){x=min(x,y);}
//
int n,m,cur;
char s[MAXN],t[MAXN];
int cnt[MAXN],tot;

namespace T1{
	ll f[MAXN];
	void solve(){
		f[0]=f[1]=1;
		rep(i,2,n)f[i]=f[i-1],add(f[i],f[i-2]);

		ll ans=f[n-2];add(ans,f[n]);
		cout<<ans<<endl;
	}
};

ll f[MAXN],g[MAXN],sum[MAXN];

int main(){

	cin>>n>>m>>(s+1);
	int flag=1;
	rep(i,2,m)flag &= (s[i]==s[1]);
	

	if(flag){
		T1::solve();
		exit(0);
	}
	for(int i=1;i<=m;){
		if(s[i] == s[1])t[++cur] = s[i],i++;
		else{
			int j=i;while(s[j] == s[i])j++;
			t[++cur]=s[i];
			i=j;
		}
	}

	int pre=0;
	rep(i,1,cur)if(t[i] != t[1]){
		cnt[++tot]=i-pre-1;
		pre=i;
	}
	if(pre!=cur)cnt[++tot]=cur-pre;
	//	
	ll mx=min(n-1,cnt[1]+1);

	rep(i,2,tot-1)if(odd(cnt[i]))tomin(mx,cnt[i]);
	if(s[m] != s[1]){
		if(odd(cnt[tot]))tomin(mx,cnt[tot]);
	}
	mx++; // 每一段只能取 2~mx 之间的偶数

	if(odd(mx))mx--;
	if(mx<2){
		cout<<"0\n";
		return 0;
	}
	mx/=2; // 每一段取 [1,mx] 之间的数

	g[0]=sum[0]=1;
	rep(i,1,n){
		g[i] = sum[i-1];
		if(i > mx)sub(g[i],sum[i-mx-1]);

		sum[i]=sum[i-1];
		add(sum[i],g[i]);
	}
	rep(i,0,n)if(even(i))f[i]=g[i/2];

	//
	ll ans=0;

	rep(len,1,n-1)if(odd(len) && len<=mx*2-1){
		ll ways=len+1; //有len+1种放置方式

		add(ans,ways*f[n-len-1]%mod);
	}
	cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result