2019 Multi-University Training Contest 2

#include<bits/stdc++.h>
#define ll long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 3e5+5;
const ll M = 998244353;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
ll qpow(ll a,ll b) {ll s=1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1;}return s; }
ll res[3005];
void init()
{
    int n = 3000;
    ll inv3 = qpow(3,M-2);
    rep(i,1,n){
        res[i] = i*(i-1)%M*inv3%M;
    }
}
 
int main()
{
    fastio();
    init(); int n;
    while(cin>>n){
        ll ans = 0;
        rep(i,1,n){
            ans = (ans + res[i])%M;
        }
        ans = ans * qpow(n,M-2) % M;
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 3e5+5;
const ull base = 19260817;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
ull hs[maxn],bs[maxn];
char s[maxn];ll ans[maxn];
inline ull HASH(int l,int r) {return hs[r] - hs[l-1]*bs[r-l+1];}
struct Palindromes_Automation
{
    int last,n,sz,trans[maxn][26],fail[maxn],cnt[maxn],len[maxn],s[maxn],pos[maxn];
    char t[maxn];
    void init()
    {
        memset(trans,0,sizeof(trans));
        memset(cnt,0,sizeof(cnt));
        memset(len,0,sizeof(len));
        memset(ans,0,sizeof(ans));
        last=0,sz=1;
        len[0] = 0,len[1] = -1;
        fail[0] = 1,fail[1] = 0;
    }
    int get_fail(int x) {while(s[n]!=s[n-len[x]-1])x=fail[x];return x;}
    void extend()
    {
        int fa = get_fail(last);
        int c = s[n];
        if(!trans[fa][c]){
            len[++sz] = len[fa] + 2;
            fail[sz] = trans[get_fail(fail[fa])][c];
            trans[fa][c] = sz;
        }
        last = trans[fa][c];
        cnt[last]++;
        pos[last] = n;
    }
    void solve(char str[])
    {
        memcpy(t,str,sizeof(t));
        int l = strlen(t+1); s[0] = 26;
        rep(i,1,l) hs[i] = hs[i-1]*base + t[i];
        for(n=1;n<=l;n++){
            s[n] = t[n] - 'a';
            extend();
        }
        per(i,sz,0) cnt[fail[i]] += cnt[i];
        rep(i,2,sz){
            int tmp = pos[i];
            if(len[i]%2==0){
                if(HASH(tmp-len[i]+1,tmp-len[i]/2)==HASH(tmp-len[i]/2+1,tmp)) ans[len[i]]+=cnt[i];
            }else{
                if(HASH(tmp-len[i]+1,tmp-len[i]/2)==HASH(tmp-len[i]/2,tmp)) ans[len[i]]+=cnt[i];
            }
        }
        rep(i,1,l){
            cout<<ans[i];
            if(i==l) cout<<endl;
            else cout<<" ";
        }
    }
}pam;
 
int main()
{
    fastio();
    bs[0] = 1; rep(i,1,maxn-1) bs[i] = bs[i-1]*base;
    while(cin>>s+1){
        pam.init();
        pam.solve(s);
    }
    return 0;
}