結果
問題 | No.1100 Boxes |
ユーザー |
![]() |
提出日時 | 2020-06-27 13:59:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,895 ms / 2,000 ms |
コード長 | 4,296 bytes |
コンパイル時間 | 1,888 ms |
コンパイル使用メモリ | 174,764 KB |
実行使用メモリ | 162,948 KB |
最終ジャッジ日時 | 2024-07-05 09:06:32 |
合計ジャッジ時間 | 18,289 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include "bits/stdc++.h"#include<vector>#include<iostream>#include<queue>#include<algorithm>#include<map>#include<set>#include<iomanip>#include<assert.h>#include<unordered_map>#include<unordered_set>#include<string>#include<stack>#include<complex>#include<memory>#pragma warning(disable:4996)using namespace std;using ld = long double;template<class T>using Table = vector<vector<T>>;const ld eps=1e-9;using Graph=vector<vector<int>>;using ll=long long;#define WHATS(var)cout<<__LINE__<<' '<<#var<<"="<<var<<endl;template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){os << "( " << v.first << ", " << v.second << ")"; return os;}template<class T> ostream& operator <<(ostream &os, const vector<T> &v){for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;}template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;}template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;}template<class T> ostream& operator <<(ostream &os, const set<T> &v){int i=0;for(auto it:v){if(i > 0){os << ' ';}os << it;i++;}return os;}using ll=long long;using ld = long double;#include<vector>const ll mod = 998244353;ll mod_pow(ll a, ll n) {ll res = 1;while (n) {if (n & 1)res = res * a%mod;a = a * a%mod; n >>= 1;}return res;}ll mod_inverse(ll a) {return mod_pow(a, mod - 2);}ll root[24], invroot[24];void init() {static bool flag=false;if(!flag){flag=true;for(int i=0;i<24;++i) {int n = (1 << i);root[i] = mod_pow(3, (mod - 1) / n);invroot[i] = mod_inverse(root[i]);}}}typedef vector <ll> poly;poly dft(poly f, bool inverse = false) {init();int n = f.size(); int i, j, k;//bit左右反転for (i = 0, j = 1; j < n - 1; j++) {for (k = n >> 1; k >(i ^= k); k >>= 1);if (i > j)swap(f[i], f[j]);}for (int j = 1; (1 << j) <= n; j++) {int m = 1 << j;ll zeta = root[j];if (inverse)zeta = invroot[j];for (i = 0; i < n; i += m) {ll powzeta = 1;for (k = i; k < i + m / 2; k++) {ll t1 = f[k], t2 = powzeta * f[k + m / 2] % mod;f[k] = t1 + t2; while (f[k] >= mod)f[k] -= mod;f[k + m / 2] = t1 - t2 + mod; while (f[k + m / 2] >= mod)f[k + m / 2] -= mod;(powzeta *= zeta) %= mod;}}}if (inverse) {ll rv = mod_inverse(n);for (i = 0; i < n; i++) {(f[i] *= rv) %= mod;}}return f;}poly multiply(poly g, poly h) {int n = 1;int pi = 0, qi = 0;for(int i=0;i<g.size();++i)if (g[i])pi = i;for(int i=0;i<h.size();++i)if (h[i])qi = i;int sz = pi + qi + 2;while (n < sz)n *= 2;g.resize(n); h.resize(n);/*while (g.size() < n) {g.push_back(0);}while (h.size() < n) {h.push_back(0);}*/poly gg = dft(g);poly hh = dft(h);poly ff; ff.resize(n);for(int i=0;i<n;++i){ff[i] = gg[i] * hh[i] % mod;}return dft(ff, true);}int main() {ios::sync_with_stdio(false);cin.tie();init();int N,K;cin>>N>>K;ll now=1;vector<ll>p1(K+1);// 1/1 32/2 243/6 1024/24 ...for(int i=0;i<=K;++i){p1[i]=mod_pow(i+1,N)*now%mod;now=now*mod_pow(i+2,mod-2);now%=mod;}vector<ll>p2(K+1);// 1/1 1/(-1) 2/1 6/(-1) ...now=1;for(int i=0;i<=K;++i){p2[i]=now;now*=mod_pow(i+1,mod-2);now%=mod;now*=mod-1;now%=mod;}//WHATS(p1)// WHATS(p2)auto p=multiply(p1,p2);ll fac=1;//WHATS(p)for(int i=0;i<p.size();++i){p[i]*=fac;p[i]%=mod;fac=fac*(i+2)%mod;}vector<ll>facts(max(N,K)+1);vector<ll>invs(max(N,K)+1);facts[0]=1;facts[1]=1;invs[0]=1;invs[1]=1;for(int i=2;i<=max(N,K);++i){facts[i]=facts[i-1]*i%mod;invs[i]=invs[i-1]*mod_pow(i,mod-2)%mod;}ll answer=0;for(int i=1;i<=N;++i){if(K>=i&&(K-i)%2==1){answer+=p[i-1]*facts[K]%mod*invs[K-i]%mod*invs[i]%mod;answer%=mod;}}cout<<answer<<endl;//WHATS(p)return 0;}