結果
問題 | No.2159 Filling 4x4 array |
ユーザー | maroon_kuri |
提出日時 | 2022-12-29 18:27:07 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,140 ms / 5,000 ms |
コード長 | 10,506 bytes |
コンパイル時間 | 3,101 ms |
コンパイル使用メモリ | 249,120 KB |
実行使用メモリ | 46,080 KB |
最終ジャッジ日時 | 2024-05-03 16:32:06 |
合計ジャッジ時間 | 56,092 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,007 ms
46,080 KB |
testcase_01 | AC | 1,001 ms
45,952 KB |
testcase_02 | AC | 1,011 ms
46,080 KB |
testcase_03 | AC | 1,140 ms
46,080 KB |
testcase_04 | AC | 1,003 ms
45,952 KB |
testcase_05 | AC | 997 ms
45,952 KB |
testcase_06 | AC | 1,005 ms
46,080 KB |
testcase_07 | AC | 1,015 ms
46,016 KB |
testcase_08 | AC | 997 ms
45,952 KB |
testcase_09 | AC | 1,007 ms
45,952 KB |
testcase_10 | AC | 1,004 ms
45,952 KB |
testcase_11 | AC | 1,015 ms
45,824 KB |
testcase_12 | AC | 1,001 ms
45,824 KB |
testcase_13 | AC | 1,005 ms
45,952 KB |
testcase_14 | AC | 1,021 ms
45,952 KB |
testcase_15 | AC | 1,020 ms
45,952 KB |
testcase_16 | AC | 1,026 ms
46,080 KB |
testcase_17 | AC | 1,005 ms
46,024 KB |
testcase_18 | AC | 1,047 ms
45,952 KB |
testcase_19 | AC | 1,010 ms
45,952 KB |
testcase_20 | AC | 1,017 ms
45,952 KB |
testcase_21 | AC | 1,033 ms
45,952 KB |
testcase_22 | AC | 1,004 ms
45,952 KB |
testcase_23 | AC | 1,002 ms
45,952 KB |
testcase_24 | AC | 1,015 ms
45,952 KB |
testcase_25 | AC | 1,003 ms
45,952 KB |
testcase_26 | AC | 1,008 ms
45,952 KB |
testcase_27 | AC | 1,004 ms
45,952 KB |
testcase_28 | AC | 1,007 ms
45,952 KB |
testcase_29 | AC | 1,003 ms
45,952 KB |
testcase_30 | AC | 1,009 ms
46,024 KB |
testcase_31 | AC | 1,004 ms
45,952 KB |
testcase_32 | AC | 1,008 ms
45,824 KB |
testcase_33 | AC | 1,018 ms
46,080 KB |
testcase_34 | AC | 998 ms
46,020 KB |
testcase_35 | AC | 1,007 ms
45,952 KB |
testcase_36 | AC | 1,010 ms
45,952 KB |
testcase_37 | AC | 1,002 ms
46,024 KB |
testcase_38 | AC | 1,008 ms
45,952 KB |
testcase_39 | AC | 1,004 ms
45,824 KB |
testcase_40 | AC | 1,012 ms
46,020 KB |
testcase_41 | AC | 1,009 ms
46,080 KB |
testcase_42 | AC | 1,007 ms
45,952 KB |
testcase_43 | AC | 1,007 ms
46,020 KB |
testcase_44 | AC | 1,004 ms
45,824 KB |
testcase_45 | AC | 1,014 ms
45,824 KB |
testcase_46 | AC | 1,021 ms
45,824 KB |
testcase_47 | AC | 1,022 ms
45,952 KB |
testcase_48 | AC | 1,012 ms
45,824 KB |
testcase_49 | AC | 1,020 ms
46,080 KB |
ソースコード
#ifndef LOCAL #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; using ll=long long; //#define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;} template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" "; dmpr(os,args...); } #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } template<class t> void print(t x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template<class t,class u> void print(const pair<t,u>&p,int suc=1){ print(p.a,2); print(p.b,suc); } template<class t,class u> void print_offset(const pair<t,u>&p,ll off,int suc=1){ print(p.a+off,2); print(p.b+off,suc); } template<class T> void print(const vector<T>&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } template<class T> void print_offset(const vector<T>&v,ll off,int suc=1){ rep(i,v.size()) print(v[i]+off,i==int(v.size())-1?suc:2); } template<class T,size_t N> void print(const array<T,N>&v,int suc=1){ rep(i,N) print(v[i],i==int(N)-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } //#define CAPITAL /* void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif }*/ void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int botbit(ull a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } int popcount(ull t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)<<i)-1; } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution<ll>(l, r)(gen); } template<class t> void myshuffle(vc<t>&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc<int> readGraph(int n,int m){ vvc<int> g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc<int> readTree(int n){ return readGraph(n,n-1); } vc<ll> presum(const vi&a){ vc<ll> s(si(a)+1); rep(i,si(a))s[i+1]=s[i]+a[i]; return s; } //mint107 は verify してねえ //#define DYNAMIC_MOD struct modinfo{uint mod,root; #ifdef DYNAMIC_MOD constexpr modinfo(uint m,uint r):mod(m),root(r),im(0){set_mod(m);} ull im; constexpr void set_mod(uint m){ mod=m; im=ull(-1)/m+1; } uint product(uint a,uint b)const{ ull z=ull(a)*b; uint x=((unsigned __int128)z*im)>>64; uint v=uint(z)-x*mod; return v<mod?v:v+mod; } #endif }; template<modinfo const&ref> struct modular{ static constexpr uint const &mod=ref.mod; static modular root(){return modular(ref.root);} uint v; //modular(initializer_list<uint>ls):v(*ls.bg){} modular(ll vv=0){s(vv%mod+mod);} modular& s(uint vv){ v=vv<mod?vv:vv-mod; return *this; } modular operator-()const{return modular()-*this;} modular& operator+=(const modular&rhs){return s(v+rhs.v);} modular&operator-=(const modular&rhs){return s(v+mod-rhs.v);} modular&operator*=(const modular&rhs){ #ifndef DYNAMIC_MOD v=ull(v)*rhs.v%mod; #else v=ref.product(v,rhs.v); #endif return *this; } modular&operator/=(const modular&rhs){return *this*=rhs.inv();} modular operator+(const modular&rhs)const{return modular(*this)+=rhs;} modular operator-(const modular&rhs)const{return modular(*this)-=rhs;} modular operator*(const modular&rhs)const{return modular(*this)*=rhs;} modular operator/(const modular&rhs)const{return modular(*this)/=rhs;} modular pow(ll n)const{ if(n<0)return inv().pow(-n); modular res(1),x(*this); while(n){ if(n&1)res*=x; x*=x; n>>=1; } return res; } modular inv()const{return pow(mod-2);} /*modular inv()const{ int x,y; int g=extgcd<ll>(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return modular(x); }*/ friend modular operator+(ll x,const modular&y){ return modular(x)+y; } friend modular operator-(ll x,const modular&y){ return modular(x)-y; } friend modular operator*(ll x,const modular&y){ return modular(x)*y; } friend modular operator/(ll x,const modular&y){ return modular(x)/y; } friend ostream& operator<<(ostream&os,const modular&m){ return os<<m.v; } friend istream& operator>>(istream&is,modular&m){ ll x;is>>x; m=modular(x); return is; } bool operator<(const modular&r)const{return v<r.v;} bool operator==(const modular&r)const{return v==r.v;} bool operator!=(const modular&r)const{return v!=r.v;} explicit operator bool()const{ return v; } }; #ifndef DYNAMIC_MOD extern constexpr modinfo base{998244353,3}; //extern constexpr modinfo base{1000000007,0}; //modinfo base{1,0}; #ifdef USE_GOOD_MOD static_assert(base.mod==998244353); #endif #else modinfo base(1,0); extern constexpr modinfo base107(1000000007,0); using mint107=modular<base107>; #endif using mint=modular<base>; mint parity(int i){ return i%2==0?1:-1; } #ifdef LOCAL const int vmax=1010; #else const int vmax=(1<<21)+10; #endif mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){ fact[0]=1; rng(i,1,vmax){ fact[i]=fact[i-1]*i; } finv[vmax-1]=fact[vmax-1].inv(); for(int i=vmax-2;i>=0;i--){ finv[i]=finv[i+1]*(i+1); } for(int i=vmax-1;i>=1;i--){ invs[i]=finv[i]*fact[i-1]; } } mint choose(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } /* const int vmax=110; mint binbuf[vmax][vmax]; mint choose(int n,int k){ return binbuf[n-k][k]; } mint binom(int a,int b){ return binbuf[a][b]; } void initfact(){ binbuf[0][0]=1; rep(i,vmax)rep(j,vmax){ if(i)binbuf[i][j]+=binbuf[i-1][j]; if(j)binbuf[i][j]+=binbuf[i][j-1]; } } */ mint p2[vmax],p2inv[vmax]; void initp2(){ p2[0]=1; rep(i,vmax-1)p2[i+1]=p2[i]*2; p2inv[vmax-1]=p2[vmax-1].inv(); per(i,vmax-1)p2inv[i]=p2inv[i+1]*2; } void slv(){ using A=array<int,8>; map<A,mint> cnt; { A cur{}; auto dfs=[&](auto self,int i)->void{ if(i==16){ cnt[cur]+=1; }else{ self(self,i+1); cur[i/4]++; cur[i%4+4]++; self(self,i+1); cur[i/4]--; cur[i%4+4]--; } }; dfs(dfs,0); } vi tar=readvi(8,-4); //cerr<<si(cnt)<<endl; vc<mint> dp(1<<16),nx(1<<16); dp[0]=1; rep(lv,30){ fill(all(nx),mint(0)); for(const auto&[key,val]:cnt){ int src=0,dst=0; auto adddif=[&](int i,int b){ int p=(key[i]^(tar[i]>>lv))&1; int from=p+b*2,to=(key[i]+from)>>1; src+=from<<(i*2); dst+=to<<(i*2); }; auto subdif=[&](int i,int b){ int p=(key[i]^(tar[i]>>lv))&1; int from=p+b*2,to=(key[i]+from)>>1; src-=from<<(i*2); dst-=to<<(i*2); }; rep(i,8)adddif(i,0); rep(bit,1<<8){ nx[dst]+=val*dp[src]; rep(i,8)if(bit&1<<i){ subdif(i,1); adddif(i,0); }else{ subdif(i,0); adddif(i,1); break; } } } dp.swap(nx); } print(dp[0]); } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); //int t;cin>>t;rep(_,t) slv(); }