QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#765209 | #9625. 魔弹 | 275307894a# | WA | 2ms | 6104kb | C++14 | 1.9kb | 2024-11-20 13:08:21 | 2024-11-20 13:08:27 |
Judging History
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'