Submission #1211087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211087		yangbaich	Dstorv (FXCUP3_dstorv)	C++20	100 / 100	397 ms	392220 KiB

dstorv

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
const int mod=1e9+7;
char s[N];
long long f[N][N];
long long g[N][N];
inline long long qmod(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int main()
{
	int n,r,h;
	cin>>n>>r>>h;
	scanf("%s",s+1);
	int a,b;
	cin>>a>>b;
	long long w1=1LL*r*qmod(r+h,mod-2)%mod;
	long long w2=(1LL-w1+mod)%mod;
//	cout<<w1<<" "<<w2<<"\n";
	f[0][b]=1;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='R')
		{
			for(int j=1;j<=n;j++)
			{
				f[i][j]=(f[i-1][j]*w1%mod+f[i][j-1]*w2%mod)%mod;		
			}
		}
		else
		{
			for(int j=0;j<n;j++)
			{
				f[i][j]=f[i-1][j+1];
			}
		}
	}
	g[n+1][a]=1;
	for(int i=n;i>=1;i--)
	{
		if(s[i]=='H')
		{
			for(int j=1;j<=n;j++)
			{
				g[i][j]=(g[i+1][j]*w2%mod+g[i][j-1]*w1%mod)%mod;		
			}
		}
		else
		{
			for(int j=0;j<n;j++)
			{
				g[i][j]=g[i+1][j+1];
			}
		}
	}
	long long ans=0;
	for(int i=0;i<=n;i++)
	{
//		cout<<f[i][0]<<" "<<g[i+1][0]<<"\n";
		ans=(ans+f[i][0]*g[i+1][0]%mod)%mod;
	}
	cout<<ans;
}

Compilation message (stderr)

dstorv.cpp: In function 'int main()':
dstorv.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%s",s+1);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 29 / 29
• Subtask 3: 62 / 62