QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#768499#9625. 魔弹chenxinyang2006TL 4ms16868kbC++234.2kb2024-11-21 11:24:142024-11-21 11:24:20

Judging History

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

  • [2024-11-21 11:24:20]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:16868kb
  • [2024-11-21 11:24:14]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}
Z fact[1000005],ifac[1000005],inv[1000005];

Z C(int N,int M){
    if(N < M || M < 0) return 0;
    return fact[N] * ifac[M] * ifac[N - M];
}

void init(int L){
    fact[0] = 1;
    rep(i,1,L) fact[i] = fact[i - 1] * i;
    ifac[L] = 1 / fact[L];
    per(i,L - 1,0) ifac[i] = ifac[i + 1] * (i + 1);
    rep(i,1,L) inv[i] = ifac[i] * fact[i - 1];
}
int n;
char s[100005];

Z ans[2][100005],answer[100005];

int main(){
//    freopen("test.in","r",stdin);
    scanf("%d",&n);
    scanf("%s",s + 1);
    init(n);
    ans[0][0] = ans[1][n + 1] = 1;
    rep(i,1,n){
        if(s[i] != 'L') continue;
        ans[0][i] = 1;
        rep(j,1,i) if(s[j] == 'R') ans[0][i] *= 1 - inv[i - j + 1];
    }
    rep(i,1,n){
        if(s[i] != 'R') continue;
        ans[1][i] = 1;
        rep(j,i,n) if(s[j] == 'L') ans[1][i] *= 1 - inv[j - i + 1];
    }
    rep(i,0,n){
        answer[i] += ans[0][i] * ans[1][i + 1] * fact[n];
        answer[i + 1] += ans[0][i] * ans[1][i + 1] * fact[n];
    }
    rep(i,1,n) printf("%d ",answer[i].val());
    printf("\n");
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 16840kb

input:

2
RL

output:

1 1 

result:

ok single line: '1 1 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 16860kb

input:

4
LLRR

output:

0 24 24 0 

result:

ok single line: '0 24 24 0 '

Test #3:

score: 0
Accepted
time: 0ms
memory: 16772kb

input:

4
RLRL

output:

9 6 6 9 

result:

ok single line: '9 6 6 9 '

Test #4:

score: 0
Accepted
time: 3ms
memory: 16864kb

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: 0ms
memory: 16836kb

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: 0
Accepted
time: 0ms
memory: 16848kb

input:

998
RLRLRLRLRLRLRLRLRLRLRLRLRLRLRRLLRRRLRLLRLLRLRLRLLLRLRRLRLRLRLRLRLRLRLRLRLRLRLRLRRLRLLRLRLRLRLRLRLRLRRLRLLRLRLRLRLRLRLRRLRRLRRRLLRLLRLRLLRRLRLLLRLRLRRLRRLRLRLRRLRLRLLRLRLRLRLRLRLRLLRLRLRLRLRLLLRRLLRLRRLRRLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRRRLRRLRLRRLRLRLRLRLRLRLRLLRLLRRLRRLRLLRLRLRLRRLLRLRLRLLRRLRL...

output:

791892921 222105954 222105954 387243673 387243673 858332170 858332170 668690160 668690160 29037702 29037702 344898397 344898397 10138435 10138435 920091431 920091431 680236417 680236417 884390492 884390492 338820980 338820980 508576275 508576275 957551010 957551010 2459479 2459479 0 0 61773050 61773...

result:

ok single line: '791892921 222105954 222105954 ... 632970969 632970969 464724562 '

Test #7:

score: 0
Accepted
time: 0ms
memory: 16860kb

input:

998
RLRLRLRLRLRLRLRLRLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRRLRLRLRLRLRLRLRLRLRLRLRLRLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRRLRLRLRLRLRLRLRLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

439674742 509947875 509947875 815063904 815063904 891776804 891776804 553641803 553641803 13450200 13450200 267859496 267859496 385670319 385670319 882911667 882911667 109331874 109331874 0 128425033 128425033 836729978 836729978 854828800 854828800 123260213 123260213 415537062 415537062 26751346 2...

result:

ok single line: '439674742 509947875 509947875 ... 773862752 498604661 498604661 '

Test #8:

score: 0
Accepted
time: 0ms
memory: 16736kb

input:

1000
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRL...

output:

255385 255385 948987885 948987885 944375949 944375949 391954880 391954880 918617102 918617102 509797789 509797789 963771001 963771001 168738152 168738152 967324970 967324970 550867915 550867915 149529568 149529568 490172856 490172856 731868859 731868859 286624466 286624466 277467460 277467460 496196...

result:

ok single line: '255385 255385 948987885 948987... 705333897 705333897 531622062 '

Test #9:

score: 0
Accepted
time: 4ms
memory: 16712kb

input:

998
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

54273261 54273261 171633438 171633438 946148426 946148426 982991957 982991957 138042735 138042735 703892213 703892213 165685072 165685072 890250227 890250227 244374543 244374543 640936104 640936104 169345002 169345002 847600184 847600184 889380235 889380235 648465375 648465375 412924715 412924715 37...

result:

ok single line: '54273261 54273261 171633438 17...38 171633438 54273261 54273261 '

Test #10:

score: 0
Accepted
time: 4ms
memory: 16756kb

input:

999
RLRRLRRRLLLLLLLRRRRLRLLRLRRLLLLRRLLRRRRLRRLRLLRRRLLLLLLRLLRRLRRLLRRRRLLLLRRRLRLRRLLLRRLLLRLLLRRLRRLRRRLLRLRRLRRLLLRLRLLRLRRLLRRRRRLRRRLRRLRLLRLLLLLLLRLLRLLLRRRRLRRLRLLLRRRLRLLRRLRLLRLRLRLLLRRLLLLRLRRRLLLLLLRRLLRLLLRRLRRRRRLLLRLRRLRLLLLRLLLRLLLRRRRLRLRRLRLLLLRLRLRLRLRLLRLLLLLLRRRLLLLLRRLLLLRLLLLR...

output:

831921527 841981814 841981814 0 802033891 802033891 0 0 0 0 0 0 0 0 313870399 313870399 0 0 0 845084145 845084145 0 202490903 202490903 292802290 292802290 0 0 0 0 246685715 246685715 0 0 750008183 750008183 0 0 0 627041700 627041700 0 129985167 129985167 0 414419357 414419357 0 0 0 0 0 0 0 69839104...

result:

ok single line: '831921527 841981814 841981814 ...451543 0 0 73252857 73252857 0 '

Test #11:

score: 0
Accepted
time: 4ms
memory: 16868kb

input:

1000
RRLRRLRLRLLRRRLRLRLRLLLRLLLRLRLLRLRRRLRRRRLLRLLLLRLLRLLRLRLRLLLLRRRRRLRLLLRLLRLRRLRLLLRRLLLLLRLRRRRLRRRLLLLRRLRLLLLLRRRRLLRLRLRLLRRRRRLLRRLRLRLLLLRRRRRLRRLLRRRLRRRRLRLLRRLLRRRLLLLRLLLLRRRRLRLLLLLRRRRLLLRLLRLRLRLRLRLRLRRLLLLRRRLRLLLRLLRRLRRRLLLLLLLLLLLRLLLLLLLRLLLRLRRLRLLLRLLRLLLLRLRLRLRLLRLRLLR...

output:

511795335 0 69779310 69779310 0 739828205 739828205 753376067 753376067 0 701671563 701671563 0 0 212012731 212012731 878780187 878780187 579239850 579239850 0 0 522816863 522816863 0 0 334242623 334242623 863711626 863711626 0 643092447 643092447 851181131 851181131 0 0 561587102 561587102 0 0 0 0 ...

result:

ok single line: '511795335 0 69779310 69779310 ... 186342784 186342784 663982717 '

Test #12:

score: -100
Time Limit Exceeded

input:

100000
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...

output:


result: