Submission #19723130


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
 
#define rng(x) x.begin(), x.end()
#define maxi(x, y) x = max(x, (y))
#define mini(x, y) x = min(x, (y))
#define pb push_back
#define F first
#define S second
#define el '\n'
#define ll long long
#define SZ(x) ((int)(x).size()) 
template<typename T>
istream&operator>>(istream&is,vector<T>&v){for(auto&it:v)is>>it;return is;}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.F << "," << P.S << ")"; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
    os << "[ "; for(auto v : V) os << v << " "; return os << "]"; }
template<class T> ostream& operator<<(ostream &os, set<T> S){
    os << "{ "; for(auto s:S) os<<s<<" "; return os<<"}"; }
#ifndef ONLINE_JUDGE 
#define db(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define db(...)
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr<<name<<" : "<<arg1<<'\n';}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names,comma-names)<<" : "<<arg1<<" |";__f(comma+1, args...);}
typedef pair<int,int> pi; typedef vector<int> vi; typedef vector<vi> vvi;
 
/*-----------------------------Code Begins--------------------------------*/

const int mod = 998244353;

int add(int x, int y){
    x += y;
    while(x >= mod) x -= mod;
    while(x < 0) x += mod;
    return x;
}

int sub(int x, int y){
    return add(x, -y);
}

int mul(int x, int y){
	x %= mod, y %= mod;
    return (x * 1ll * y) % mod;
}

int binPow(int x, int y){
    int z = 1;
    while(y){
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

int inv(int x){
    return binPow(x, mod - 2);
}

int divide(int x, int y){
    return mul(x, inv(y));
}



void solve(){
	int n; cin >> n;
    vi pow2(n + 1);
    pow2[0] = 1;
    for(int i = 1; i < n + 1; ++i){
    	pow2[i] = mul(pow2[i - 1], 2);
    }

    vi st(n + 1);
    for(int t = 1; 2 * t + 1 <= n; ++t){
    	st[t] = add(st[t - 1], mul(pow2[2 * t - 1], 2 * (2 * t + 1)));
    }

    int d = inv(mul(pow2[n], 2)), ex = mul(pow2[n], n);

    for(int x = 1; x <= n; ++x){
    	int t = min(x - 1 - 1, n - x - 1);
    	int ans = ex;
    	if(t > 0){
    		ans = add(ans, st[t]);
    	}
    	cout << mul(ans, d) << el;
    }
}
 
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

Submission Info

Submission Time
Task E - 1D Reversi Builder
User inder128
Language C++ (GCC 9.2.1)
Score 700
Code Size 2655 Byte
Status AC
Exec Time 38 ms
Memory 4712 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 36
Set Name Test Cases
Sample sample.txt, sample_2.txt, sample_3.txt
All 1.txt, 103497.txt, 1068.txt, 1188.txt, 133447.txt, 15.txt, 163982.txt, 168417.txt, 199997.txt, 199998.txt, 199999.txt, 2.txt, 200000.txt, 22.txt, 22886.txt, 242.txt, 3.txt, 31932.txt, 36426.txt, 4.txt, 48772.txt, 5.txt, 55.txt, 6.txt, 60522.txt, 6344.txt, 7.txt, 7685.txt, 7775.txt, 8.txt, 85160.txt, 9.txt, 95728.txt, sample.txt, sample_2.txt, sample_3.txt
Case Name Status Exec Time Memory
1.txt AC 4 ms 3564 KB
103497.txt AC 19 ms 3972 KB
1068.txt AC 9 ms 3592 KB
1188.txt AC 3 ms 3632 KB
133447.txt AC 22 ms 4232 KB
15.txt AC 4 ms 3572 KB
163982.txt AC 29 ms 4320 KB
168417.txt AC 32 ms 4292 KB
199997.txt AC 35 ms 4704 KB
199998.txt AC 38 ms 4712 KB
199999.txt AC 34 ms 4612 KB
2.txt AC 9 ms 3616 KB
200000.txt AC 33 ms 4584 KB
22.txt AC 9 ms 3488 KB
22886.txt AC 7 ms 3724 KB
242.txt AC 4 ms 3544 KB
3.txt AC 2 ms 3564 KB
31932.txt AC 9 ms 3624 KB
36426.txt AC 9 ms 3436 KB
4.txt AC 2 ms 3488 KB
48772.txt AC 11 ms 3616 KB
5.txt AC 4 ms 3592 KB
55.txt AC 2 ms 3572 KB
6.txt AC 2 ms 3572 KB
60522.txt AC 18 ms 3636 KB
6344.txt AC 11 ms 3652 KB
7.txt AC 2 ms 3612 KB
7685.txt AC 5 ms 3656 KB
7775.txt AC 5 ms 3660 KB
8.txt AC 3 ms 3600 KB
85160.txt AC 17 ms 3896 KB
9.txt AC 5 ms 3552 KB
95728.txt AC 18 ms 3868 KB
sample.txt AC 10 ms 3592 KB
sample_2.txt AC 2 ms 3540 KB
sample_3.txt AC 2 ms 3436 KB