QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504745#9112. Zayin and RafflePhantomThreshold#TL 0ms0kbC++202.6kb2024-08-04 15:32:082024-08-04 15:32:09

Judging History

你现在查看的是最新测评结果

  • [2024-08-04 15:32:09]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-08-04 15:32:08]
  • 提交

answer

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

typedef long long ll;
const ll mod=1000000007;
const ll denomi=1000000000;

inline ll ksm(ll a,ll x){
	ll ret=1;
	for (;x;x>>=1,a=a*a%mod) if (x&1) ret=ret*a%mod;
	return ret;	
}
inline ll inv(ll a){
	return ksm(a,mod-2);	
}

ll n,m,K;
ll p[15];
ll sump[1050];
ll a[100050][10];
ll f[66000][260];
ll dp[67000];

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> K;
	for (int i=0;i<K;i++) cin >> p[i];
	for (int i=0;i<K;i++) p[i]=p[i]*inv(denomi)%mod;
	
	for (ll mask=0;mask<(1LL<<K);mask++){
		sump[mask]=0;
		for (ll sel=0;sel<K;sel++){
			if ((mask>>sel)&1){
				sump[mask]=(sump[mask]+p[sel])%mod;	
			}
		}
	}
//	cerr << "stage1" << endl;
	for (ll i=1;i<=n;i++){
		for (ll j=0;j<K;j++){
			cin >> a[i][j];
		}
		for (ll mask=0;mask<(1LL<<K);mask++){
			ll sum=0;
			for (ll sel=0;sel<K;sel++) if ((mask>>sel)&1) sum|=a[i][sel];
			f[sum][mask]++;
		}
	}
//	cerr << "stage2" << endl;
	ll N=(1LL<<m);
	ll NK=(1LL<<K);
	
//	cerr << "----------------" << endl;
//	for (int i=0;i<N;i++){
//		for (int j=0;j<4;j++) cerr << f[i][j] << " ";
//		cerr << endl;	
//	}
//	cerr << "----------------" << endl;
	
	for (ll d=1;d<N;d<<=1){
		for (ll mid=d<<1,i=0;i<N;i+=mid){
			for (ll j=0;j<d;j++){
				for (ll _=0;_<NK;_++){
					ll x=f[i+j][_],y=f[i+j+d][_];
					f[i+j+d][_]=x+y;
				}
			}
		}
	}
	
//	cerr << "----------------" << endl;
//	for (int i=0;i<N;i++){
//		for (int j=0;j<4;j++) cerr << f[i][j] << " ";
//		cerr << endl;	
//	}
//	cerr << "----------------" << endl;
//	
//	cerr << "stage3" << endl;
	
	for (ll sel=0;sel<N;sel++){
		for (ll d=1;d<NK;d<<=1){
			for (ll mid=d<<1,i=0;i<NK;i+=mid){
				for (ll j=0;j<d;j++){
					ll x=f[sel][i+j],y=f[sel][i+j+d];
					f[sel][i+j]=x-y;	
				}
			}
		}
	}
	
//	cerr << "----------------" << endl;
//	for (int i=0;i<N;i++){
//		for (int j=0;j<4;j++) cerr << f[i][j] << " ";
//		cerr << endl;	
//	}
//	cerr << "----------------" << endl;
//	
//	cerr << "stage4" << endl;
	for (ll sel=0;sel<N;sel++){
		dp[sel]=1;
		for (ll d=0;d<NK;d++){
			dp[sel]=dp[sel]*ksm(sump[d],f[sel][d])%mod;
		}
	}
	
//	cerr << "----------------" << endl;
//	for (int i=0;i<N;i++){
//		cerr << dp[i] << " ";
//	}
//	cerr << endl;
//	cerr << "----------------" << endl;
	
//	cerr << "stage5" << endl;
	for (ll d=1;d<N;d++){
		for (ll mid=d<<1,i=0;i<N;i+=mid){
			for (ll j=0;j<d;j++){
				ll x=dp[i+j],y=dp[i+j+d];
				dp[i+j+d]=((y-x)%mod+mod)%mod;
			}
		}
	}
//	cerr << "stage6" << endl;
	for (ll sel=0;sel<N;sel++){
		cout << dp[sel] << "\n";	
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

100000 16 8
14837 17850 15180 22820 26722 4874 4574 999893143
15006 45877 19815 26604 6797 0 25449 15769
26395 0 495 64118 18133 47822 5863 39708
56443 188 55498 14620 36924 25033 0 36587
55421 21544 59411 3280 55222 0 51028 55986
42323 41153 53683 16144 53188 15759 0 28378
63709 51900 0 18592 1916 ...

output:


result: