QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#765209#9625. 魔弹275307894a#WA 2ms6104kbC++141.9kb2024-11-20 13:08:212024-11-20 13:08:27

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 13:08:27]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6104kb
  • [2024-11-20 13:08:21]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e5+5,M=N*4+5,K=1000+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n;
char s[N];
ll inv[N],f1[N],f2[N],frc[N],frv[N];
ll C(int x,int y){return frc[x]*frv[y]%mod*frv[x-y]%mod;}
void Solve(){
	scanf("%d%s",&n,s+1);
	inv[1]=1;for(int i=2;i<=n;i++) inv[i]=(mod-inv[mod%i])*(mod/i)%mod;
	for(int i=frc[0]=frv[0]=1;i<=n;i++) frc[i]=frc[i-1]*i%mod,frv[i]=frv[i-1]*inv[i]%mod;
	f1[0]=1;
	for(int i=1;i<=n;i++)if(s[i]=='L'){
		f1[i]=frc[i-1];
		for(int j=1;j<i;j++) if(s[j]=='L') f1[i]=f1[i]*(1+inv[i-j])%mod;
	}
	f2[n+1]=1;
	for(int i=n;i;i--) if(s[i]=='R'){
		f2[i]=frc[n-i];
		for(int j=i+1;j<=n;j++) if(s[j]=='R') f2[i]=f2[i]*(1+inv[j-i])%mod;
	}
	s[0]='L';s[n+1]='R';
	for(int i=1;i<=n;i++){
		ll w=0;
		if(s[i]=='L'&&s[i+1]=='R') w=f1[i]*f2[i+1]%mod*C(n,i)%mod;
		if(s[i]=='R'&&s[i-1]=='L') w=f1[i-1]*f2[i]%mod*C(n,i-1)%mod;
		printf("%lld%c",w," \n"[i==n]);
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 6096kb

input:

2
RL

output:

1 1

result:

ok single line: '1 1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 6096kb

input:

4
LLRR

output:

0 24 24 0

result:

ok single line: '0 24 24 0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 6100kb

input:

4
RLRL

output:

9 6 6 9

result:

ok single line: '9 6 6 9'

Test #4:

score: 0
Accepted
time: 1ms
memory: 6096kb

input:

10
LRLRLLRRRR

output:

1088640 1088640 604800 604800 0 1935360 1935360 0 0 0

result:

ok single line: '1088640 1088640 604800 604800 0 1935360 1935360 0 0 0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 6104kb

input:

10
LLRLLRLRLL

output:

0 725760 725760 0 725760 725760 483840 483840 0 1693440

result:

ok single line: '0 725760 725760 0 725760 725760 483840 483840 0 1693440'

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 5980kb

input:

998
RLRLRLRLRLRLRLRLRLRLRLRLRLRLRRLLRRRLRLLRLLRLRLRLLLRLRRLRLRLRLRLRLRLRLRLRLRLRLRLRRLRLLRLRLRLRLRLRLRLRRLRLLRLRLRLRLRLRLRRLRRLRRRLLRLLRLRLLRRLRLLLRLRLRRLRRLRLRLRRLRLRLLRLRLRLRLRLRLRLLRLRLRLRLRLLLRRLLRLRRLRRLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRRRLRRLRLRRLRLRLRLRLRLRLRLLRLLRRLRRLRLLRLRLRLRRLLRLRLRLLRRLRL...

output:

32595344 376578802 376578802 590190283 590190283 571258252 571258252 109101294 109101294 866691134 866691134 523721359 523721359 320260038 320260038 623571289 623571289 944248727 944248727 397356809 397356809 92796570 92796570 331153899 331153899 823368619 823368619 73007855 73007855 0 0 968206714 9...

result:

wrong answer 1st lines differ - expected: '791892921 222105954 222105954 ...0 632970969 632970969 464724562', found: '32595344 376578802 376578802 5...0 929817805 929817805 192562981'