結果
| 問題 |
No.2231 Surprising Flash!
|
| コンテスト | |
| ユーザー |
 fastmath
|
| 提出日時 | 2023-02-24 22:59:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 20,077 bytes |
| コンパイル時間 | 3,108 ms |
| コンパイル使用メモリ | 171,304 KB |
| 最終ジャッジ日時 | 2025-02-10 22:09:17 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 |
| other | AC * 29 WA * 13 RE * 2 |
ソースコード
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define x first
#define y second
#define Time (double)clock()/CLOCKS_PER_SEC
#ifdef LOCAL
#define debug(x) std::cerr << #x << ": " << x << '\n';
#define debug2(x, y) std::cerr << #x << ", " << #y << ": " << x << ", " << y << '\n';
#define debug3(x, y, z) std::cerr << #x << ", " << #y << ", " << #z << ": " << x << ", " << y << ", " << z << '\n';
#else
#define debug(x)
#define debug2(x, y)
#define debug3(x, y, z)
#endif
#define FORI(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR(i,a) FORI(i,0,a)
#define ROFI(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define ROF(i,a) ROFI(i,0,a)
#define rep(a) FOR(_,a)
#define each(a,x) for (auto& a: x)
#define FORN(i, n) FORI(i, 1, n + 1)
using vi = vector<int>;
template <typename T>
std::istream& operator >>(std::istream& input, std::pair <T, T> & data)
{
input >> data.x >> data.y;
return input;
}
template <typename T>
std::istream& operator >>(std::istream& input, std::vector<T>& data)
{
for (T& x : data)
input >> x;
return input;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const pair <T, T> & data)
{
output << "(" << data.x << "," << data.y << ")";
return output;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const std::vector<T>& data)
{
for (const T& x : data)
output << x << " ";
return output;
}
ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
ll math_mod(ll a, ll b) { return a - b * div_down(a, b); }
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0;
} // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0;
}
ll gcd(ll a, ll b) {
while (b) {
tie(a, b) = mp(b, a % b);
}
return a;
}
int Bit(int mask, int bit) { return (mask >> bit) & 1; }
const int md = 998244353;
namespace faq{
inline void add(int &x, int y) {
x += y;
if (x >= md) {
x -= md;
}
}
inline void sub(int &x, int y) {
x -= y;
if (x < 0) {
x += md;
}
}
inline int mul(int x, int y) {
return (long long) x * y % md;
}
inline int power(int x, int y) {
int res = 1;
for (; y; y >>= 1, x = mul(x, x)) {
if (y & 1) {
res = mul(res, x);
}
}
return res;
}
inline int inv(int a) {
a %= md;
if (a < 0) {
a += md;
}
int b = md, u = 0, v = 1;
while (a) {
int t = b / a;
b -= t * a;
swap(a, b);
u -= t * v;
swap(u, v);
}
if (u < 0) {
u += md;
}
return u;
}
namespace ntt {
int base = 1, root = -1, max_base = -1;
vector<int> rev = {0, 1}, roots = {0, 1};
void init() {
int temp = md - 1;
max_base = 0;
while (temp % 2 == 0) {
temp >>= 1;
++max_base;
}
root = 2;
while (true) {
if (power(root, 1 << max_base) == 1 && power(root, 1 << max_base - 1) != 1) {
break;
}
++root;
}
}
void ensure_base(int nbase) {
if (max_base == -1) {
init();
}
if (nbase <= base) {
return;
}
assert(nbase <= max_base);
rev.resize(1 << nbase);
for (int i = 0; i < 1 << nbase; ++i) {
rev[i] = rev[i >> 1] >> 1 | (i & 1) << nbase - 1;
}
roots.resize(1 << nbase);
while (base < nbase) {
int z = power(root, 1 << max_base - 1 - base);
for (int i = 1 << base - 1; i < 1 << base; ++i) {
roots[i << 1] = roots[i];
roots[i << 1 | 1] = mul(roots[i], z);
}
++base;
}
}
void dft(vector<int> &a) {
int n = a.size(), zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for (int i = 0; i < n; ++i) {
if (i < rev[i] >> shift) {
swap(a[i], a[rev[i] >> shift]);
}
}
for (int i = 1; i < n; i <<= 1) {
for (int j = 0; j < n; j += i << 1) {
for (int k = 0; k < i; ++k) {
int x = a[j + k], y = mul(a[j + k + i], roots[i + k]);
a[j + k] = (x + y) % md;
a[j + k + i] = (x + md - y) % md;
}
}
}
}
vector<int> multiply(vector<int> a, vector<int> b) {
int need = a.size() + b.size() - 1, nbase = 0;
while (1 << nbase < need) {
++nbase;
}
ensure_base(nbase);
int sz = 1 << nbase;
a.resize(sz);
b.resize(sz);
bool equal = a == b;
dft(a);
if (equal) {
b = a;
} else {
dft(b);
}
int inv_sz = inv(sz);
for (int i = 0; i < sz; ++i) {
a[i] = mul(mul(a[i], b[i]), inv_sz);
}
reverse(a.begin() + 1, a.end());
dft(a);
a.resize(need);
return a;
}
vector<int> inverse(vector<int> a) {
int n = a.size(), m = n + 1 >> 1;
if (n == 1) {
return vector<int>(1, inv(a[0]));
} else {
vector<int> b = inverse(vector<int>(a.begin(), a.begin() + m));
int need = n << 1, nbase = 0;
while (1 << nbase < need) {
++nbase;
}
ensure_base(nbase);
int sz = 1 << nbase;
a.resize(sz);
b.resize(sz);
dft(a);
dft(b);
int inv_sz = inv(sz);
for (int i = 0; i < sz; ++i) {
a[i] = mul(mul(md + 2 - mul(a[i], b[i]), b[i]), inv_sz);
}
reverse(a.begin() + 1, a.end());
dft(a);
a.resize(n);
return a;
}
}
}
using ntt::multiply;
using ntt::inverse;
vector<int>& operator += (vector<int> &a, const vector<int> &b) {
if (a.size() < b.size()) {
a.resize(b.size());
}
for (int i = 0; i < b.size(); ++i) {
add(a[i], b[i]);
}
return a;
}
vector<int> operator + (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c += b;
}
vector<int>& operator -= (vector<int> &a, const vector<int> &b) {
if (a.size() < b.size()) {
a.resize(b.size());
}
for (int i = 0; i < b.size(); ++i) {
sub(a[i], b[i]);
}
return a;
}
vector<int> operator - (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c -= b;
}
vector<int>& operator *= (vector<int> &a, const vector<int> &b) {
if (min(a.size(), b.size()) < 128) {
vector<int> c = a;
a.assign(a.size() + b.size() - 1, 0);
for (int i = 0; i < c.size(); ++i) {
for (int j = 0; j < b.size(); ++j) {
add(a[i + j], mul(c[i], b[j]));
}
}
} else {
a = multiply(a, b);
}
return a;
}
vector<int> operator * (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c *= b;
}
vector<int>& operator /= (vector<int> &a, const vector<int> &b) {
int n = a.size(), m = b.size();
if (n < m) {
a.clear();
} else {
vector<int> c = b;
reverse(a.begin(), a.end());
reverse(c.begin(), c.end());
c.resize(n - m + 1);
a *= inverse(c);
a.erase(a.begin() + n - m + 1, a.end());
reverse(a.begin(), a.end());
}
return a;
}
vector<int> operator / (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c /= b;
}
vector<int>& operator %= (vector<int> &a, const vector<int> &b) {
int n = a.size(), m = b.size();
if (n >= m) {
vector<int> c = (a / b) * b;
a.resize(m - 1);
for (int i = 0; i < m - 1; ++i) {
sub(a[i], c[i]);
}
}
return a;
}
vector<int> operator % (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c %= b;
}
vector<int> derivative(const vector<int> &a) {
int n = a.size();
vector<int> b(n - 1);
for (int i = 1; i < n; ++i) {
b[i - 1] = mul(a[i], i);
}
return b;
}
vector<int> primitive(const vector<int> &a) {
int n = a.size();
vector<int> b(n + 1), invs(n + 1);
for (int i = 1; i <= n; ++i) {
invs[i] = i == 1 ? 1 : mul(md - md / i, invs[md % i]);
b[i] = mul(a[i - 1], invs[i]);
}
return b;
}
vector<int> logarithm(const vector<int> &a) {
vector<int> b = primitive(derivative(a) * inverse(a));
b.resize(a.size());
return b;
}
vector<int> exponent(const vector<int> &a) {
vector<int> b(1, 1);
while (b.size() < a.size()) {
vector<int> c(a.begin(), a.begin() + min(a.size(), b.size() << 1));
add(c[0], 1);
vector<int> old_b = b;
b.resize(b.size() << 1);
c -= logarithm(b);
c *= old_b;
for (int i = b.size() >> 1; i < b.size(); ++i) {
b[i] = c[i];
}
}
b.resize(a.size());
return b;
}
vector<int> power(const vector<int> &a, int m) {
int n = a.size(), p = -1;
vector<int> b(n);
for (int i = 0; i < n; ++i) {
if (a[i]) {
p = i;
break;
}
}
if (p == -1) {
b[0] = !m;
return b;
}
if ((long long) m * p >= n) {
return b;
}
int mu = power(a[p], m), di = inv(a[p]);
vector<int> c(n - m * p);
for (int i = 0; i < n - m * p; ++i) {
c[i] = mul(a[i + p], di);
}
c = logarithm(c);
for (int i = 0; i < n - m * p; ++i) {
c[i] = mul(c[i], m);
}
c = exponent(c);
for (int i = 0; i < n - m * p; ++i) {
b[i + m * p] = mul(c[i], mu);
}
return b;
}
vector<int> sqrt(const vector<int> &a) {
vector<int> b(1, 1);
while (b.size() < a.size()) {
vector<int> c(a.begin(), a.begin() + min(a.size(), b.size() << 1));
vector<int> old_b = b;
b.resize(b.size() << 1);
c *= inverse(b);
for (int i = b.size() >> 1; i < b.size(); ++i) {
b[i] = mul(c[i], md + 1 >> 1);
}
}
b.resize(a.size());
return b;
}
vector<int> multiply_all(int l, int r, vector<vector<int>> &all) {
if (l > r) {
return vector<int>();
} else if (l == r) {
return all[l];
} else {
int y = l + r >> 1;
return multiply_all(l, y, all) * multiply_all(y + 1, r, all);
}
}
vector<int> evaluate(const vector<int> &f, const vector<int> &x) {
int n = x.size();
if (!n) {
return vector<int>();
}
vector<vector<int>> up(n * 2);
for (int i = 0; i < n; ++i) {
up[i + n] = vector<int>{(md - x[i]) % md, 1};
}
for (int i = n - 1; i; --i) {
up[i] = up[i << 1] * up[i << 1 | 1];
}
vector<vector<int>> down(n * 2);
down[1] = f % up[1];
for (int i = 2; i < n * 2; ++i) {
down[i] = down[i >> 1] % up[i];
}
vector<int> y(n);
for (int i = 0; i < n; ++i) {
y[i] = down[i + n][0];
}
return y;
}
vector<int> interpolate(const vector<int> &x, const vector<int> &y) {
int n = x.size();
vector<vector<int>> up(n * 2);
for (int i = 0; i < n; ++i) { up[i + n] = vector<int>{(md - x[i]) % md, 1};
}
for (int i = n - 1; i; --i) {
up[i] = up[i << 1] * up[i << 1 | 1];
}
vector<int> a = evaluate(derivative(up[1]), x);
for (int i = 0; i < n; ++i) {
a[i] = mul(y[i], inv(a[i]));
}
vector<vector<int>> down(n * 2);
for (int i = 0; i < n; ++i) {
down[i + n] = vector<int>(1, a[i]);
}
for (int i = n - 1; i; --i) {
down[i] = down[i << 1] * up[i << 1 | 1] + down[i << 1 | 1] * up[i << 1];
}
return down[1];
}
}
struct SuffixArray {
vector <int> sa, lcp;
SuffixArray (string &s, int lim=256) {
int n = (int)s.size() + 1, k = 0, a, b;
vector <int> x(s.begin(), s.end() + 1), y(n), ws(max(n, lim)), rank(n);
sa = lcp = y, iota(sa.begin(), sa.end(), 0);
for (int j = 0, p = 0; p < n; j = max(1ll, j * 2), lim = p) {
p = j, iota(y.begin(), y.end(), n - j);
for (int i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
fill(ws.begin(), ws.end(), 0);
for (int i = 0; i < n; i++) ws[x[i]]++;
for (int i = 1; i < lim; i++) ws[i] += ws[i - 1];
for (int i = n; i--; ) sa[--ws[x[y[i]]]] = y[i];
swap(x, y), p = 1, x[sa[0]] = 0;
for (int i = 1; i < n; i++) a = sa[i - 1], b = sa[i], x[b] = (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
}
for (int i = 1; i < n; i++) rank[sa[i]] = i;
for (int i = 0, j; i < n - 1; lcp[rank[i++]]=k)
for (k && k--, j = sa[rank[i] - 1];
s[i + k] == s[j + k]; k++);
}
};
struct Rmq {
const int INF = 1e9;
vi rmq;
int sz;
Rmq(){}
void build(int n) {
sz = 1;
while (sz < n) sz *= 2;
rmq.assign(sz * 2, INF);
}
Rmq(int n) {
sz = 1;
while (sz < n) sz *= 2;
rmq.assign(sz * 2, INF);
}
void put(int i, int x) {
i += sz;
ckmin(rmq[i], x);
for (i/= 2; i; i/= 2) {
rmq[i] = min(rmq[i * 2], rmq[i * 2 + 1]);
}
}
int getMin(int l, int r) { //[l;r)
assert(l < r);
r--;
l += sz;
r += sz;
int res = INF;
while(l < r) {
if (l%2 == 1) res = min(res, rmq[l]);
if (r%2==0) res = min(res, rmq[r]);
l = (l + 1)/2;
r = (r - 1) /2;
}
if (l == r) res = min(res, rmq[l]);
return res;
}
};
struct Lc {
vi pos;
Rmq rmq;
void build(string s) {
SuffixArray sa(s);
auto ss = sa.sa;
ss.erase(ss.begin());
auto lcp = sa.lcp;
lcp.erase(lcp.begin());
lcp.erase(lcp.begin());
pos.resize(s.size());
assert(s.size() == ss.size());
FOR (i, ss.size()) {
pos[ss[i]] = i;
}
int n = s.size();
assert(lcp.size() == n - 1);
rmq.build(n - 1);
FOR (i, n - 1) {
rmq.put(i, lcp[i]);
}
}
int getLcp(int i, int j) {
i = pos[i]; j = pos[j];
if (j < i) {
swap(i, j);
}
if (i == j) {
return 1e18;
}
else {
return rmq.getMin(i, j);
}
}
};
template<int MOD, int RT> struct mint {
static const int mod = MOD;
static constexpr mint rt() { return RT; } // primitive root for FFT
int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
mint() { v = 0; }
mint(ll _v) { v = (int)((-MOD < _v && _v < MOD) ? _v : _v % MOD);
if (v < 0) v += MOD; }
friend bool operator==(const mint& a, const mint& b) {
return a.v == b.v; }
friend bool operator!=(const mint& a, const mint& b) {
return !(a == b); }
friend bool operator<(const mint& a, const mint& b) {
return a.v < b.v; }
friend string ts(mint a) { return to_string(a.v); }
mint& operator+=(const mint& m) {
if ((v += m.v) >= MOD) v -= MOD;
return *this; }
mint& operator-=(const mint& m) {
if ((v -= m.v) < 0) v += MOD;
return *this; }
mint& operator*=(const mint& m) {
v = (int)((ll)v*m.v%MOD); return *this; }
mint& operator/=(const mint& m) { return (*this) *= inv(m); }
friend mint pow(mint a, ll p) {
mint ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans; }
mint & operator ^=(const int &p) { return (*this) = pow(this, p); }
friend mint inv(const mint& a) { assert(a.v != 0);
return pow(a,MOD-2); }
mint operator-() const { return mint(-v); }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
friend mint operator^(mint a, const int p) { return pow(a, p); }
};
const int MOD = 998244353;
typedef mint<MOD,5> mi; // 5 is primitive root for both common mods
typedef vector<mi> vmi;
std::ostream& operator << (std::ostream& o, const mi& a)
{
cout << a.v;
return o;
}
vector<vmi> scmb; // small combinations
void genComb(int SZ) {
scmb.assign(SZ,vmi(SZ)); scmb[0][0] = 1;
FORI(i,1,SZ) FOR(j,i+1)
scmb[i][j] = scmb[i-1][j]+(j?scmb[i-1][j-1]:0);
}
vmi invs, fac, ifac; // make sure to convert to LL before doing any multiplications ...
void genFac(int SZ) {
invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ);
invs[1] = fac[0] = ifac[0] = 1;
FORI(i,2,SZ) invs[i] = mi(-(ll)MOD/i*(int)invs[MOD%i]);
FORI(i,1,SZ) {
fac[i] = fac[i-1]*i;
ifac[i] = ifac[i-1]*invs[i];
}
}
mi comb(int a, int b) {
if (a < b || b < 0) return 0;
assert(a < fac.size());
return fac[a]*ifac[b]*ifac[a-b];
}
mi partNonNegative(int a, int b) {
assert(a >= 0);
if (a == 0 && b == 0) {
return 1;
}
else {
return comb(a + b - 1, b - 1);
}
}
mi partPositive(int a, int b) {
assert(a >= 0);
if (a == 0 && b == 0) {
return 1;
}
else {
return comb(a - 1, b - 1);
}
}
signed main() {
#ifdef LOCAL
#else
#define endl '\n'
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
auto solve = [&] () {
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
string tot=s;
each (c,tot)if(c=='?')c='a';
tot += t;
Lc lc;
lc.build(tot);
vi vals(n), vals2(n), valt(m), valt2(m);
FOR (i, n) {
if (s[i] != '?') {
vals[i] = s[i] - 'a' + 1;
}
vals2[i] = vals[i] * vals[i];
}
FOR (i, m) {
valt[i] = t[i] - 'a' + 1;
valt2[i] = valt[i] * valt[i];
}
reverse(all(valt));
reverse(all(valt2));
vmi pre(n + 1);
FOR(i,n){
pre[i + 1] = pre[i] + mi(vals[i]) * mi(vals[i]) * mi(vals[i]);
}
vi p;
using namespace faq;
auto mu = vals2 * valt * vi({-2}) + vals * valt2;
for (int l = 0; l + t.size() <= s.size(); ++l) {
mi x = mu[l + m - 1] + pre[l + m] - pre[l];
if (x.v==0) {
p.app(l);
}
}
if (p.empty()) {
cout<<-1<<endl;
return;
}
auto comp1 = [&] (int l, int r) {
int ans = 0;
auto go = [&] (int i, int j, int len) {
auto k = lc.getLcp(i,j);
if (k < len) {
assert(tot[i + k]!=tot[j+k]);
if (s[i+k]<s[j+k]) {
ans = 1;
}
else {
ans = -1;
}
}
};
go(n, l, r - l);
if (ans == 1) return true;
else if (ans == -1) return false;
go(n + (r - l), n, m - (r - l));
if (ans == 1) return true;
else if (ans == -1) return false;
go(l + m, n + (l + m - r), r - l);
if (ans == 1) return true;
else if (ans == -1) return false;
return false;
/*
int k = lc.getLcp(n,l);
int os = r - l;
if (k < os) {
return t[k] < s[l+k];
}
int cur = os;
k = lc.getLcp(n, n + os);
os = m - os;
if (k < os) {
return t[cur + k] < t[k];
}
cur = l + m - r;
k = lc.getLcp(n + cur, l + m);
os =
*/
};
auto comp = [&] (int i, int j) {
if (j < i) {
return !comp1(j,i);
}
else {
return comp1(i,j);
}
};
debug(p);
int opt = p[0];
p.erase(p.begin());
each (i, p) {
if (comp(i,opt)) {
opt = i;
}
}
FOR (i, m) {
s[opt + i] = t[i];
}
each (c, s) if (c == '?') c = 'a';
cout << s << endl;
};
int t;
cin >> t;
rep (t) {
solve();
}
}