QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504745 | #9112. Zayin and Raffle | PhantomThreshold# | TL | 0ms | 0kb | C++20 | 2.6kb | 2024-08-04 15:32:08 | 2024-08-04 15:32:09 |
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 ...