(2022 Nioke Duo School IV) D-Jobs (Easy Version) (3D prefix or)

Title:

Sample input:

3 52 1 1 2 2 1 23 1 3 2 2 3 1 2 3 32 2 3 1 3 2 1191415411

Sample output:

34417749

The meaning of the question: There are n companies, and the i-th company has mi jobs. Each job has numerical requirements for three abilities, and all three abilities must meet the standards to be qualified for the job.As long as a person is competent for any job in a company, he can enter the company.

Q times of inquiries, each time a triplet, representing the values ​​of a person's three abilities, ask how many companies this person can go to work, and force online.

We can't do the prefix sum for every company because 10*400*400*400 will definitely time out, since we just need to know if we canCompetent for a certain job of a certain company, not all jobs, and we want to store the information of multiple companies, so we only need to maintain it with binary, for the t th companyWe use the t-th bit to maintain this information, so that we can make complementary interference between companies.Then it can be directly O(1) query.

Here is the code:

#include#include#include#include#include#include using namespace std;const int N=401,mod=998244353;int f[N][N][N],s[2000005];int lastans=0,seed;inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int main(){int n,m;n=read();m=read();for(int i=1;i<=n;i++){int t;t=read();for(int j=1;j<=t;j++){int a,b,c;a=read(),b=read(),c=read();f[a][b][c]|=(1<u(1,400);std::mt19937 rng(seed);s[0]=1;for(int i=1;i<=m;i++)s[i]=1ll*s[i-1]*seed%mod;long long anss = 0;for(int i=1;i<=m;i++){int IQ=(u(rng)^lastans)%400+1; // The IQ of the i-th friendint EQ=(u(rng)^lastans)%400+1; // The EQ of the i-th friendint AQ=(u(rng)^lastans)%400+1; // The AQ of the i-th friendlastans=0;for(int i=1;i<=n;i++)lastans+=f[IQ][EQ][AQ]>>i&1;anss = (anss+1ll*lastans*s[m-i]%mod)%mod;}printf("%lld\n", anss);return 0;}