沈阳集训day3

#include <iostream>
#include<cstdio>
  
using namespace std;
const int bas = 2333, maxn = 1000005;
int n, rightpos,has[maxn], base[maxn];
char s[maxn];
void init(){
    base[0] = 1;
    for(int i = 1; i <= n; i++)
        has[i] = has[i-1] * bas + s[i-1], base[i] = base[i-1] * bas;
}
bool check(int pos){
    int st1, ed1, a, b , c, d;
    if(pos == 1){
        a = has[n/2+1]-has[1]*base[n/2], c = has[n] - has[n/2+1]*base[n/2];
        b = d = 0;
    }
    else if(pos == n){
        a = has[n/2], c = has[n-1] - has[n/2] * base[n/2];
        b = d = 0;
    }
     else if(pos == n/2 +1){
        a = has[n/2], c = has[n] - has[n/2+1]*base[n-n/2-1];
        b = d = 0;
    }
    else if(pos <= n/2){
        st1 = n/2 + 1;
        ed1 = n/2 + pos,
        a = has[pos-1], b = has[n/2+1] - has[pos]*base[n/2-pos+1];
        c = has[ed1] - has[st1]*base[ed1-st1], d = has[n] - has[ed1]*base[n-ed1];
    }
    else if(pos > n/2){
        st1 = pos-n/2-1;
        a = has[st1], b = has[n/2] - has[st1]*base[n/2-st1];
        c = has[pos-1] - has[n/2]*base[pos-1-n/2], d = has[n]-has[pos]*base[n-pos];
    }
     
    if((a==c) && (b==d)){
        rightpos = pos;return 1;
    }
    return 0;
  
  
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        int cnt = 0;
        scanf("%d", &n);
        scanf("%s", s);
        init();
        int fg1 = 0, fg2 = 0;
        if(n%2 == 0){
            puts("NOT POSSIBLE");
            continue;
        }
        for(int i = 1; i <= n/2; i++)
            if(check(i)){
                fg1 = 1;break;
            }
        for(int i = n/2+2; i <= n; i++)
            if(check(i)){
                fg2 = 1; break;
            }
         
        if(fg1 && fg2)
            if(check(n/2+1)) cnt = 1;
                else cnt = 2;
        else if(fg1 || fg2) cnt = 1; 
         
        if(check(n/2+1))cnt = 1;
        if(cnt == 1){
            if(rightpos <= n/2){
                 for(int i = 1; i <= n/2+1; i++)
                     if(i!=rightpos)printf("%c",s[i-1]);
            }      
           else {
               for(int i = n/2+1; i <= n; i++)
                  if(i!=rightpos)printf("%c", s[i-1]);    
            }
                printf("\n");   
        }
        else if(cnt > 1)puts("NOT UNIQUE");
        else puts("NOT POSSIBLE");
    }
}

#include<iostream>
#include<cstdio>
#define p 998244353
#define ll long long
using namespace std;
const int maxn = 1e7 + 5;
ll fac[maxn];
ll a, b, k, n;
ll ans;
ll mi(long long a,long long b)
{
    long long anss=1;
    for(;b;b>>=1,a=a*a%p)
       if(b&1) anss=anss*a%p;
    return anss;
}
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x=1;y=0;return a;
    }
    ll x0, y0;
    ll d = exgcd(b, a%b, x0, y0);
    x = y0;
    y = x0 - (a/b)*y0;
    return d;
}
ll in(ll a){
    ll x, y;
    exgcd(a, p, x, y);
    return (x%p + p) %p;
}
ll C(ll pp, ll q){
    return fac[n] * in(fac[pp]) % p * in(fac[n-pp])  % p * fac[n] %p * in(fac[q]) %p *in(fac[n-q]) % p;
}
int main ( ) {
    scanf ( "%lld%lld%lld%lld", &n, &a, &b, &k );
    fac[0] = 1;
    for(ll i = 1; i <= n; i++)
        fac[i] = fac[i-1]*i % p;
    if(a==0&&b!=0) swap(a,b);
    if(!a && !b&&k!=0) ;
    else if(!a&&!b&&!k)
      ans=mi(4,n);
    else if(!b){
        int fg = 0;
        if(k % a) fg = 1;
        int t = k/a;
        if(fg == 0)
            ans = fac[n] * in(fac[t]) % p * in(fac[n-t]) % p*mi(2,n)%p;
                 
    }
    else {
        for(ll i = 0; i <= n; i++)
            if(i * a > k)break;
            else if( (k - a*i) % b == 0){
                ll t = (k - a*i) / b;
                if(t <= n)ans = (ans + C(i , t)) % p;
                //printf("%lld  ", ans);
            }   
    }
    printf ("%lld", ans);
    return 0;
}