C++14(g++5.4) 解法, 执行用时: 443ms, 内存消耗: 179128K, 提交时间: 2020-02-02 17:50:07

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,m,q,xx,yy,now,nex,tim,vis[1100000],len,beg,sta[1100000],l,r,mi;
long long num[1100000][21],k,preiod[1100000][21],ci;
bool e[21][21];
int main(){
	scanf("%d%d%d",&n,&m,&q);
	fo(i,1,n){
		scanf("%d",&xx);
		if (xx==1){
			now|=1<<(i-1);
			num[0][i]++;//num[i][0]++;
		}
	}
	fo(i,0,(1<<n)-1) vis[i]=-1;
	vis[now]=0;
	sta[0]=now;
	fo(i,1,m){
		scanf("%d%d",&xx,&yy);
		e[xx][yy]=1;
	}
	while (1){
		nex=0;
		fo(i,1,n)
			if (now&(1<<(i-1)))
				fo(j,1,n)
					if (e[i][j])
						nex^=1<<(j-1);
		if (vis[nex]!=-1){
			len=tim+1-vis[nex];
			beg=vis[nex];
			break;
		}
		vis[nex]=++tim;
		sta[tim]=nex;
		now=nex;
		fo(i,1,n){
			num[tim][i]=num[tim-1][i];
			if (now&(1<<(i-1))) num[tim][i]++;
		}
	}
//	printf("%d %d\n",beg,len);
	fo(i,1,len){
		fo(j,1,n){
			preiod[i][j]=num[beg+i-1][j];
			if (beg) preiod[i][j]-=num[beg-1][j];
		}
	}
	while (q--){
		scanf("%d%lld",&xx,&k);
		ci=0;//!!!!!!!!!!!!
		if (k>num[tim][xx]){
			if (!preiod[len][xx]){
				printf("-1\n");
				continue;
			}
			ci=(k-num[tim][xx]-1)/preiod[len][xx]+1;
			k-=ci*preiod[len][xx];
		}
		l=0;r=tim;
		while (l<r){
			mi=(l+r)>>1;
			if (num[mi][xx]>=k) r=mi;else l=mi+1;
		}
		printf("%lld\n",l+len*ci);
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 115ms, 内存消耗: 32472K, 提交时间: 2021-05-10 17:19:40

#include <bits/stdc++.h>
#define maxn 20
using namespace std;

vector<int> v;
int id[1 << maxn];

int n, m, q;
int in[maxn];
int pcnt[1 << maxn];
int x, y;
vector<int> a[maxn], b[maxn];
long long k;

int main(){
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 0;i < (1 << n);i++) pcnt[i] = pcnt[i >> 1] ^ (i & 1), id[i] = -1;
	int s = 0;
	for(int i = 0;i < n;i++) scanf("%d", &x), s |= x << i;
	while(m--){
		scanf("%d%d", &x, &y);
		x--, y--;
		in[y] |= 1 << x;
	}
	int st;
	while(1){
		if(id[s] != -1){
			st = id[s];
			break;	
		}
		id[s] = v.size(), v.push_back(s);
		int ss = 0; 
		for(int i = 0;i < n;i++) ss |= pcnt[s & in[i]] << i;
		s = ss;
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < st;j++) if(v[j] & (1 << i)) a[i].push_back(j);
		for(int j = st;j < v.size();j++) if(v[j] & (1 << i)) b[i].push_back(j - st);
	}
	while(q--){
		scanf("%d%lld", &x, &k), x--;
		if(b[x].empty() && a[x].size() < k){
			puts("-1");
			continue;
		}
		if(a[x].size() >= k){
			printf("%d\n", a[x][k - 1]);
			continue;
		}
		k -= a[x].size();
		long long ans = st;
		k--;
		ans += k / b[x].size() * (v.size() - st);
		k %= b[x].size();
		ans += b[x][k];
		printf("%lld\n", ans);
	}
}