JAG 夏合宿 2016 Day4 M

本番で手をつけていない問題の復習をまとめる．

問題文
以下の条件を満たす0と1から構成されるの正方行列を考える．

• 各行に含まれる1の数はは
• 各列に注目したときに1である要素の間に0の要素があってはならない．

このとき，クエリが個与えられる．

• 以上の条件を満たす正方行列について辞書順で番目の行列を出力せよ．

制約

解法

• 前計算パート

条件を満たす行列の総数を数える．

DP 各列の状態をで表す．
0: 1を未使用かつ0　
1: 1を使用中
2: 1を使用済みかつ0

遷移のパターン数を全て試すと計算量がでTLEするので，
必要な遷移だけに注目すると，計算量がに落とせる．

• クエリパート

あとはよくある辞書順貪欲で答えを求める．
答えが存在するかどうかは，前計算で配るDPではなく貰うDPでやると
1クエリあたりの計算量は

全体の計算量は

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

using ll=long long;
int n,a,b,q;

int three=1,two=1;

ll dp[12][59049];

using pii=pair<int,int>;
vector<pii> mov[59049];
bool ones[1024];
bool ok[59049];
char bit[1024][11];

inline void prepare(){
	rep(loop,n) three*=3,two*=2;

	rep(cur,three){
		int parm[10],tmp=cur,nxt=0;
		rep(i,n) parm[n-1-i]=tmp%3,tmp/=3; 
		rep(i,n) nxt=3*nxt+(parm[i]?2:0);
		if(nxt==three-1) dp[n][cur]=1LL;
	}

	rep(mask,two){
		rep(i,n){
			if(mask&(1<<(n-1-i)))
				bit[mask][i]='1';
			else
				bit[mask][i]='0';
		}
		bit[mask][n]='\0';	
	}

	rep(mask,two){
		ones[mask]=0;
		int tmp=__builtin_popcount(mask);
		if(tmp<a||b<tmp) continue;
		ones[mask]=1;
	}
			
	rep(cur,three){
		int parm[10],tmp=cur,mask=0;
		rep(i,n) parm[n-1-i]=tmp%3,tmp/=3; 
		rep(i,n) if(parm[i]!=2) mask|=(1<<i);
		
		for(int smask=mask;;smask=(smask-1)&mask){
			if(ones[smask]){
				int nxt=0;
				rep(i,n){
					nxt=3*nxt;
					if(smask&(1<<i))
						nxt+=1;
					else
						nxt+=(parm[i]?2:0);
				}
				mov[cur].push_back(pii(smask,nxt));
			}

			if(smask==0) break;
		}
		reverse(begin(mov[cur]),end(mov[cur]));
	}
}



const ll limit=1LL<<60;

//struct CWW{CWW(){ios::sync_with_stdio(false);cin.tie(0);}}cww;

int main(void){
	scanf("%d %d %d %d",&n,&a,&b,&q);
	prepare();
	
	for(int i=n-1;i>=0;--i)rep(cur,three){
		for(auto &it:mov[cur]){
			int mask=it.first,nxt=it.second;
			dp[i][cur]+=dp[i+1][nxt];
		}
	}
	
	
	rep(loop,q){
		if(loop) puts("");

		ll t;
		scanf("%lld",&t);
		if(t>dp[0][0]){
			puts("No such matrix.");
		}else{
			int cur=0;
			rep(pos,n){
				int seq=-1,tar=-1;
				for(auto &it:mov[cur]){
					int mask=it.first,nxt=it.second;
					ll nt=t-dp[pos+1][nxt];
					seq=mask,tar=nxt;
					if(nt<=0) break;
					t=nt;
				}

				puts(bit[seq]);
				cur=tar;
			}
		}
	}

	return 0;
}