NYC2015
New Year Contest2015
解けそうな奴を解き直した.
A:やるだけ
B:やるだけ
C☆:直前と異なるものを挿入→初め以外割りと何でもできる
D:対称位置にジャンプ→xと-xからdijkstra
E:
"次数がd1~dnの木 (Σdi=2*(n-1),di>0) の総数は(n-2)!/Π(di-1)! だから終わり" ふえぇ
rngさんがいってる寝ながらDPがまずわかんないんだよな
F:setの要素の1/n倍が関係ある,みたいなの
G:実装
H☆:距離hoge以上で全部に行けるように最小→端っこから張る
I☆:aから来た+bから来た-(重複分) カタラン数
J☆:踏んだマス(not 延べ)の数→Σ1-(i歩目でalready visitedな場所を踏む確率)
"i歩目でalready visitedなとこに行く"は,"直前j歩ではじめて元の場所に戻る"みたいなのの直和になる."i歩ではじめて元の場所に戻る"は,"i歩で戻る-j歩で初めて戻る*(i-j歩分)"みたいなのの和
K:構成,おもしろい
L☆:互除法はユークリッド環なら出来る(実際の割り算アルゴリズムは適宜考える(Z[i]なら複素数割り算の点からもっとも近い点を取れば良い)
M:自力で場合分けしようとしたけどk=4が闇っぽい.解けない・・・
2016/8/4追記 やっとMを解いた.
M☆:どういう連結成分がどういう順で並んでる というのを状態とする. 例えば,K=4だと {12 3 4} とか {13 24} とか {4 2 3 1} とか.この各状態に対し,その方法で塗れるかどうか というbitを決めた時の塗り方の方法というのが求まるのでそれでやろうと思ったけど,K=4で連結成分が3つのやつが36通りあるため2^36で爆発炎上した.
よく考えると,2^36全部試さなくても,"長さの範囲をどういうsetで作れるか"が変わる部分で分けた区間を考える.この区間の数をMとすると,Mは高々2^K+K-1.(∵区間を分けるところは,各2^K set(0は除く)のとりうる値の範囲だが,左はただのmaxになるからK通り,右が2^K -1通り) 従って各区間ごとに考えれば,M^Kの場合分けが出来る.各場合に対し,それを実現する状態の割当があるかを試して,あとはコンビネーションの(たかだか二次元くらいの)足しあわせをすると解ける.
この2^36から落とす発想としては2016年のICPC国内予選Gとかと似てて,各円に入ってるかどうか みたいなのを考えると2^N状態あるけど実際平面に書くと高々N^2箇所しか状態がない みたいに, 実際にあり得る状態をうまく抑えるって感じ?(わりと一般的にありふれてるものなのでわざわざ意識しない気がするけど)
最後の足し合わせは四次元にはなるけど,自由に大きさを動かせる連結成分が高々K/2個しかないことを考えると2になる.
割当の数はordered bell number(A000670 - OEIS)そのもので,これはK!程度(ほんとはK! /(log2)^Kくらいで近似されるらしい)
よって全体の計算量は(2^K+K-1)^K * K! * 2^(K/2) とかになる やばい
長方形をx+y=一定みたいなので区切るのは,三角形の足し引きで書くと変な場合分けしなくて済む(HyperRectangle とかtco2016 R2B easyとか)
M:
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} typedef long long ll; ll mod=1e9+7; ll inv[7]; void add(ll &x,ll y){ x+=y; x%=mod; } ll C(ll x,int y){ if(x<y) return 0; ll a=1; rep(i,y) a=a*(x-i)%mod*inv[i+1]%mod; return a; } bool B(int x,int y){return (x>>y)&1;} vector<ll> xs; bool can[16][20]; ll N,a[4]; int K; int M; vector<int> asn[5][4]; int sel[4]; ll ans; void dfs(int t){ if(t>0){ bool ok=0; int A=asn[t][0].size(); rep(i,A){ bool no=0; rep(j,t) if(!can[asn[t][j][i]][sel[j]]) no=1; if(!no) ok=1; } if(ok){ // cout<<"sel= "; // rep(j,t) cout<<sel[j]<<" "; // puts(""); ll L=N+1; vector<ll> vc; rep(j,t){ L-=xs[sel[j]]; if(xs[sel[j]]+1!=xs[sel[j]+1]) vc.pb(xs[sel[j]+1]-xs[sel[j]]); } assert(vc.size()<=2); ll tmp=0; if(vc.size()==0) tmp=C(L,t); if(vc.size()==1) tmp=C(L+1,t+1)-C(L-vc[0]+1,t+1); if(vc.size()==2) tmp=C(L+2,t+2)-C(L-vc[0]+2,t+2)-C(L-vc[1]+2,t+2)+C(L-vc[0]-vc[1]+2,t+2); // show(tmp); add(ans,tmp); } } if(t==K) return; rep(i,M){ sel[t]=i; dfs(t+1); } } int bt[4]; void dfsas(int t,int left){ // show(t); // show(left); if(left==0){ rep(i,t){ asn[t][i].pb(bt[i]); } } if(t==K) return; rep(i,1<<K) if(i>0&&(i&left)==i){ bt[t]=i; dfsas(t+1,left^i); } } int main(){ rep1(i,6){ ll a=1; rep(j,i){ if(a%i==0){ inv[i]=a/i; break; } a+=mod; } } cin>>N>>K; rep(i,K) cin>>a[i]; rep(i,K) xs.pb(a[i]); rep(i,1<<K){ if(i==0) continue; ll s=0; rep(j,K) if(B(i,j)) s+=a[j]; xs.pb(s+1); } sort(all(xs)); xs.erase(unique(xs.begin(),xs.end()),xs.end()); M=xs.size(); // show(M); // show(xs); rep(i,1<<K){ if(i==0) continue; ll l=0,r=0; rep(j,K) if(B(i,j)) chmax(l,a[j]),r+=a[j]; rep(j,M){ if(l<=xs[j]&&xs[j]<=r) can[i][j]=1; } } dfsas(0,(1<<K)-1); dfs(0); if(ans<0) ans+=mod; cout<<ans<<endl; }