ひっかけ問題?
https://codeforces.com/contest/1237/problem/E
問題
整数Nが与えられる。1~Nのラベルを持つN頂点の木で、以下の条件を満たすものは何通りか。
- 完全二分木で、バランスが取れている(これ以上深さの総和を小さくできない)
- 各頂点と左の子頂点のラベルのパリティは等しい
- 各頂点と右の子頂点のラベルのパリティは異なる
解法
試しに小さなNで試してみると、1種類構築できるかできないかの2通りしか解がない。
それも解が規則的なので、実験で出してみても何となく合ってしまう。
int N; int TL[(1<<20)+10],TR[(1<<20)+10]; ll memo[1010101][2]; const ll mo=998244353; ll hoge(int L,int R,int odd) ; ll hoge2(int L,int odd) { if(memo[L][odd]>=0) return memo[L][odd]; ll ret=0; for(int i=1;i<=L;i++) if((i&1)==odd) { int a=i-1; int b=L-i; if(max(TR[a],TR[b])-min(TL[a],TL[b])<=1) { (ret+=hoge(1,i,odd^1)*hoge(i+1,L+1,odd))%=mo; } } return memo[L][odd]=ret; } ll hoge(int L,int R,int odd) { if(R-L<=0) return 1; odd ^= 1^(L&1); return hoge2(R-L,odd); } void solve() { int i,j,k,l,r,x,y; string s; /* for(i=1;i<=20;i++) TL[(1<<i)-1]++; FOR(i,21) TR[(1<<i)]++; for(i=2;i<=1<<20;i++) { TL[i]+=TL[i-1]; TR[i]+=TR[i-1]; } MINUS(memo); for(i=1;i<=1000000;i++) { ll a=hoge(1,i+1,0); if(a) cout<<i<<" "<<0<<" "<<a<<endl; ll b=hoge(1,i+1,1); if(b) cout<<i<<" "<<1<<" "<<b<<endl; } */ cin>>N; x=1; set<int> S; FOR(i,20) { if(x>N) break; S.insert(x); x++; S.insert(x); x*=2; S.insert(x); x++; S.insert(x); x*=2; x--; S.insert(x); } cout<<S.count(N)<<endl; //cout<<(hoge(1,N+1,0)+hoge(1,N+1,1))%mo<<endl; }
まとめ
なんだこれ…。