結果
| 問題 | No.1533 Don't be Negative! |
| ユーザー |
 tatyam
|
| 提出日時 | 2021-06-04 07:01:18 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 17,857 bytes |
| コンパイル時間 | 2,364 ms |
| コンパイル使用メモリ | 223,720 KB |
| 最終ジャッジ日時 | 2024-11-15 05:10:20 |
| 合計ジャッジ時間 | 3,269 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'Modint bostan_mori(Poly, Poly, ll)':
main.cpp:340:32: error: 'ceil_pow2' is not a member of 'atcoder::internal'
340 | ll lg = atcoder::internal::ceil_pow2(max(P.size(), Q.size())), z = 1 << lg;
| ^~~~~~~~~
main.cpp:341:29: error: 'z' was not declared in this scope
341 | const Modint M = Modint(z * 2).inv(), W = Modint(atcoder::internal::primitive_root<Modint::mod()>).pow(Modint::mod() - 1 >> lg + 1).inv();
| ^
main.cpp:351:49: error: 'W' was not declared in this scope
351 | for(ll i = 1; i < z; i++) w[i] = w[i - 1] * W;
| ^
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned;
using pcc = pair<char, char>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tuplis = array<ll, 3>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
const ll LINF=0x1fffffffffffffff;
const ll MINF=0x7fffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
const int MODD=998244353;
const ld DINF=numeric_limits<ld>::infinity();
const ld EPS=1e-9;
const ld PI=3.1415926535897932;
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0;i<n;++i)
#define rep2(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i<b;++i)
#define rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i=n;i--;)
#define rrep2(i,n) for(ll i=n;i--;)
#define rrep3(i,a,b) for(ll i=b;i-->(a);)
#define rrep4(i,a,b,c) for(ll i=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define each1(i,a) for(auto&&i:a)
#define each2(x,y,a) for(auto&&[x,y]:a)
#define each3(x,y,z,a) for(auto&&[x,y,z]:a)
#define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__)
#define all1(i) begin(i),end(i)
#define all2(i,a) begin(i),begin(i)+a
#define all3(i,a,b) begin(i)+a,begin(i)+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(i) (i).rbegin(),(i).rend()
#define rall2(i,k) (i).rbegin(),(i).rbegin()+k
#define rall3(i,a,b) (i).rbegin()+a,(i).rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
#define dsum(...) accumulate(all(__VA_ARGS__),0.0L)
#define Msum(...) accumulate(all(__VA_ARGS__),0_M)
#define elif else if
#define unless(a) if(!(a))
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define Sort(a) sort(all(a))
#define Rev(a) reverse(all(a))
#define Uniq(a) sort(all(a));a.erase(unique(all(a)),end(a))
#define vec(type,name,...) vector<type>name(__VA_ARGS__)
#define VEC(type,name,size) vector<type>name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }
inline ll popcnt(ull a){ return __builtin_popcountll(a); }
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmin(T& a, const U& b){ if(a > T(b)){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < T(b)){ a = b; return 1; } return 0; }
vector<ll> iota(ll n, ll begin = 0){ vector<ll> a(n); iota(a.begin(), a.end(), begin); return a; }
vector<pll> factor(ull x){ vector<pll> ans; for(ull i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
map<ll,ll> factor_map(ull x){ map<ll,ll> ans; for(ull i = 2; i * i <= x; i++) if(x % i == 0){ ans[i] = 1; while((x /= i) % i == 0) ans[i]++; } if(x != 1) ans[x] = 1; return ans; }
vector<ll> divisor(ull x){ vector<ll> ans; for(ull i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
template<class T> unordered_map<T, ll> press(vector<T> a){ Uniq(a); unordered_map<T, ll> ans; rep(a.size()) ans[a[i]] = i; return ans; }
template<class T> map<T, ll> press_map(vector<T> a){ Uniq(a); map<T, ll> ans; rep(a.size()) ans[a[i]] = i; return ans; }
int scan(){ return getchar(); }
void scan(int& a){ scanf("%d", &a); }
void scan(unsigned& a){ scanf("%u", &a); }
void scan(long& a){ scanf("%ld", &a); }
void scan(long long& a){ scanf("%lld", &a); }
void scan(unsigned long long& a){ scanf("%llu", &a); }
void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); }
void scan(float& a){ scanf("%f", &a); }
void scan(double& a){ scanf("%lf", &a); }
void scan(long double& a){ scanf("%Lf", &a); }
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){ cin >> a; }
template<class T> void scan(vector<T>&);
template<class T, size_t size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto&& i : a) scan(i); }
template<class T, size_t size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, size_t size> void scan(T (&a)[size]){ for(auto&& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void in(){}
template <class... T> void in(T&... a){ (void)initializer_list<int>{ (scan(a), 0)... }; }
void print(){ putchar(' '); }
void print(bool a){ printf("%d", a); }
void print(int a){ printf("%d", a); }
void print(unsigned a){ printf("%u", a); }
void print(long a){ printf("%ld", a); }
void print(long long a){ printf("%lld", a); }
void print(unsigned long long a){ printf("%llu", a); }
void print(char a){ printf("%c", a); }
void print(char a[]){ printf("%s", a); }
void print(const char a[]){ printf("%s", a); }
void print(float a){ printf("%.15f", a); }
void print(double a){ printf("%.15f", a); }
void print(long double a){ printf("%.15Lf", a); }
void print(const string& a){ for(auto&& i : a) print(i); }
template<class T> void print(const complex<T>& a){ if(a.real() >= 0) print('+'); print(a.real()); if(a.imag() >= 0) print('+'); print(a.imag()); print('i'); }
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
#ifdef DEBUG
inline ll __lg(ull x){ return 63 - __builtin_clzll(x); }
#define debug(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); }
#else
#define debug(...) void(0)
#endif
int first(bool i = true){ return out(i?"first":"second"); }
int First(bool i = true){ return out(i?"First":"Second"); }
int yes(bool i = true){ return out(i?"yes":"no"); }
int Yes(bool i = true){ return out(i?"Yes":"No"); }
int No(){ return out("No"); }
int YES(bool i = true){ return out(i?"YES":"NO"); }
int NO(){ return out("NO"); }
int Yay(bool i = true){ return out(i?"Yay!":":("); }
int possible(bool i = true){ return out(i?"possible":"impossible"); }
int Possible(bool i = true){ return out(i?"Possible":"Impossible"); }
int POSSIBLE(bool i = true){ return out(i?"POSSIBLE":"IMPOSSIBLE"); }
void Case(ll i){ printf("Case #%lld: ", i); }
#include <atcoder/convolution>
using Modint = atcoder::modint998244353;
struct Poly{
vector<Modint> a;
Poly(){}
explicit Poly(ll n): a(n){}
Poly(const vector<Modint>& a): a(a){}
Poly(vector<Modint>&& a): a(a){}
Modint& operator[](ll x){ return a[x]; }
Modint operator[](ll x) const { return a[x]; }
auto begin(){ return a.begin(); }
auto end(){ return a.end(); }
auto begin() const { return a.cbegin(); }
auto end() const { return a.cend(); }
ll size() const { return a.size(); }
Poly& resize(ll n){ a.resize(n); return *this; }
Poly& resize(const Poly& f){ if(size() < f.size()) resize(f.size()); return *this; }
Poly& operator+=(const Poly& f){
resize(f);
for(ll i = 0; i < f.size(); i++) a[i] += f[i];
return *this;
}
Poly operator+(const Poly& f) const {
if(size() < f.size()) return Poly(f) += *this;
return Poly(*this) += f;
}
Poly& operator-=(const Poly& f){
resize(f);
for(ll i = 0; i < f.size(); i++) a[i] -= f[i];
return *this;
}
Poly operator-(const Poly& f) const { return Poly(*this) -= f; }
Poly operator-(int) const {
Poly ans(size());
for(ll i = 0; i < size(); i++) ans[i] = -a[i];
return ans;
}
Poly& operator*=(Modint x){ for(Modint& i : a) i *= x; return *this; }
Poly operator*(Modint x){ return Poly(*this) *= x; }
Poly operator*(const Poly& f) const { return atcoder::convolution(a, f.a); }
Poly& operator*=(const Poly& f){ a = atcoder::convolution(move(a), vector(f.a)); return *this; }
Poly inv(ll n = -1) const {
if(n == -1) n = size();
if(n == 0) return {};
assert(size() && a[0] != 0);
vector<Modint> ans = {a[0].inv()};
for(ll m = 1; m < n; m *= 2) {
const Modint M = Modint(m * m * 4).inv();
vector<Modint> x(a.begin(), a.begin() + min(size(), m * 2)), y = ans;
x.resize(m * 2); atcoder::internal::butterfly(x);
y.resize(m * 2); atcoder::internal::butterfly(y);
for(ll i = 0; i < m * 2; ++i) x[i] *= y[i];
atcoder::internal::butterfly_inv(x);
for(ll i = 0; i < m; i++) x[i] = 0;
for(ll i = m; i < m * 2; i++) x[i] *= M;
atcoder::internal::butterfly(x);
for(ll i = 0; i < m * 2; ++i) x[i] *= -y[i];
atcoder::internal::butterfly_inv(x);
ans.insert(ans.end(), x.begin() + m, x.end());
}
ans.resize(n);
return ans;
}
Poly operator/=(const Poly& f){
const ll n = size();
*this *= f.inv(n);
return resize(n);
}
Poly operator/(const Poly& f) const { return Poly(*this) /= f; }
Poly div(const Poly& f) const {
assert(f.size() && f.a.back() != 0);
if(size() < f.size()) return {};
Poly x = *this, y = f;
while(x.size() && !x.a.back().val()) x.a.pop_back();
while(y.size() && !y.a.back().val()) y.a.pop_back();
const ll n = x.size() - y.size() + 1;
reverse(x.begin(), x.end()); x.resize(n);
reverse(y.begin(), y.end()); y.resize(n);
x /= y;
reverse(x.begin(), x.end());
return x;
}
Poly operator%(const Poly& f) const {
assert(f.size() && f.a.back() != 0);
return (*this - f * div(f)).resize(f.size() - 1);
}
Poly D(ll n = -1) const {
if(n == -1) n = size();
if(n == 0) return {};
Poly ans(size() - 1);
for(ll i = 1; i < size(); i++) ans[i - 1] = a[i] * Modint::raw(i);
return ans;
}
Poly integral() const {
const ll n = size();
Poly ans(n + 1);
ans[0] = 1;
for(ll i = 0; i < n; i++) ans[i + 1] = ans[i] * Modint::raw(i + 1);
ans[n] = ans[n].inv();
for(ll i = n; i--; ){
swap(ans[i], ans[i + 1]);
ans[i + 1] *= ans[i] * a[i];
ans[i] *= Modint::raw(i + 1);
}
ans[0] = 0;
return ans;
}
Poly log(ll n = -1) const {
if(n == -1) n = size();
if(n == 0) return {};
assert(size() && a[0] == 1);
return (D(n) * inv(n)).resize(n - 1).integral();
}
Poly exp(ll n = -1) const {
if(n == -1) n = size();
if(n == 0) return {};
assert(a[0] == 0);
if(size() == 1) return vector<Modint>{1};
vector<Modint> b = {1, a[1]}, c = {1}, z1, z2 = {1, 1};
for(ll m = 2; m < n; m *= 2) {
const Modint M = Modint(m).inv(), M2 = Modint(m * 2).inv();
auto y = b;
y.resize(m * 2); atcoder::internal::butterfly(y);
z1 = move(z2);
vector<Modint> z(m);
for(ll i = 0; i < m; i++) z[i] = y[i] * z1[i];
atcoder::internal::butterfly_inv(z);
for(ll i = 0; i < m / 2; i++) z[i] = 0;
for(ll i = m / 2; i < m; i++) z[i] *= M * M;
atcoder::internal::butterfly(z);
for(ll i = 0; i < m; i++) z[i] *= -z1[i];
atcoder::internal::butterfly_inv(z);
c.insert(c.end(), z.begin() + m / 2, z.end());
z2 = c; z2.resize(m * 2);
atcoder::internal::butterfly(z2);
Poly x = vector<Modint>(begin(), begin() + min(size(), m));
x = x.D(); x.a.push_back(0);
atcoder::internal::butterfly(x.a);
for(ll i = 0; i < m; i++) x[i] *= y[i] * M;
atcoder::internal::butterfly_inv(x.a);
x -= Poly(b).D();
x.resize(m * 2);
for(ll i = 0; i < m - 1; i++){
x[m + i] = x[i]; x[i] = 0;
}
atcoder::internal::butterfly(x.a);
for (ll i = 0; i < m * 2; i++) x[i] *= z2[i] * M2;
atcoder::internal::butterfly_inv(x.a);
x = x.integral(); x.a.pop_back();
for(ll i = m; i < min(size(), m * 2); i++) x[i] += a[i];
for(ll i = 0; i < m; i++) x[i] = 0;
for(ll i = m; i < m * 2; i++) x[i] *= M2;
atcoder::internal::butterfly(x.a);
for(ll i = 0; i < m * 2; ++i) x[i] *= y[i];
atcoder::internal::butterfly_inv(x.a);
b.insert(b.end(), x.begin() + m, x.end());
}
return Poly(move(b)).resize(n);
}
Poly pow(ll k, ll n = -1){
if(n == -1) n = size();
if(n == 0) return {};
assert(k >= 0);
if(k == 0){
Poly ans(n);
ans[0] = 1;
return ans;
}
Poly ans = *this;
ll cnt = 0;
while(cnt < size() && ans[cnt] == 0) cnt++;
if(cnt == size() || cnt * k >= n) return Poly(n);
ans.a.erase(ans.a.begin(), ans.a.begin() + cnt);
const Modint c = ans[0], C = c.pow(k), D = c.inv(), K = k;
for(Modint& i : ans) i *= D;
ans = ans.log(n - cnt * k);
for(Modint& i : ans) i *= K;
ans = ans.exp();
for(Modint& i : ans) i *= C;
ans.a.insert(ans.a.begin(), cnt * k, 0);
return ans;
}
};
Modint bostan_mori(Poly P, Poly Q, ll n){
assert(Q.size() && Q[0] != 0);
ll lg = atcoder::internal::ceil_pow2(max(P.size(), Q.size())), z = 1 << lg;
const Modint M = Modint(z * 2).inv(), W = Modint(atcoder::internal::primitive_root<Modint::mod()>).pow(Modint::mod() - 1 >> lg + 1).inv();
auto bitrev = [lg](ll bit){
for(ll i = 0; i < lg / 2; i++){
const ll j = lg - 1 - i;
if((bit >> i ^ bit >> j) & 1) bit ^= 1 << i | 1 << j;
}
return bit;
};
vector<Modint> w(z);
w[0] = 1;
for(ll i = 1; i < z; i++) w[i] = w[i - 1] * W;
{
vector<Modint> w2(z);
for(ll i = 0; i < z; i++) w2[bitrev(i)] = w[i];
w = move(w2);
}
while(n){
P.resize(z * 2); atcoder::internal::butterfly(P.a);
Q.resize(z * 2); atcoder::internal::butterfly(Q.a);
if(n & 1){
for(ll i = 0; i < z; i++) P[i] = (P[i << 1] * Q[i << 1 ^ 1] - P[i << 1 ^ 1] * Q[i << 1]) * w[i];
for(ll i = 0; i < z; i++) Q[i] = Q[i << 1] * Q[i << 1 ^ 1] * 2;
}
else{
for(ll i = 0; i < z; i++) P[i] = P[i << 1] * Q[i << 1 ^ 1] + P[i << 1 ^ 1] * Q[i << 1];
for(ll i = 0; i < z; i++) Q[i] = Q[i << 1] * Q[i << 1 ^ 1] * 2;
}
P.resize(z); atcoder::internal::butterfly_inv(P.a);
Q.resize(z); atcoder::internal::butterfly_inv(Q.a);
for(Modint& i : P) i *= M;
for(Modint& i : Q) i *= M;
n >>= 1;
}
return P[0] / Q[0];
}
int main(){
ll N, M, K;
cin >> N >> M >> K;
if(M == K) M--;
if(M == 0) return puts("0") & 0;
Poly F(M * 2 + 1);
ll s = 0;
for(ll i = -M; i <= M; i++) if(i != K && i != -K){
F[i + M] = 1;
s += 1;
}
Poly S(M + 1);
S[M] = s;
Poly Q = Poly(vector<Modint>{1, -1}) * (F - S) * (F - S);
cout << (F.pow(N + 2, N * M) / Q)[N * M - 1].val() << endl;
}