More than 2022 cattle guest school game 4 yue

2022In cattle guest multi-universities' game 4 yue

D.Jobs (Easy Version)

题意

$q$People looking for a job,有$n$家公司,Every company has$m$个工作,Each and every job has$3$个属性$a,b,c$,If and only if each person$a,b,c$Have more than one job$a,b,c$,This talent can successfully complete this work,If a person can complete a job in a company,Then the company will be him.Each person's attributes are made for you$seed$As the random number seed and on a person's answer,进行随机生成.

计算

$({\sum }_{i=1}^{n}an{s}_i\ast see{d}^{q-i})mod998244353$

$an{s}_i$表示第iHow many individual companies are willing to accept him

数据范围

$1⩽n⩽10$

$1⩽q⩽2\ast 10^6$

$1⩽m⩽10^5$

$1⩽a_i,b_i,c_i⩽400$

思路

由于有$q$个人了,The answer to the query one time complexity is in$\log (m\ast n)$,Can think first pretreatment out to the company$i$The ability of a value can be up to, 然后$O(1)$进行查询.

预处理,The four dimensions$bool$Array would burst memory,所以用$bitset$进行压位,$dp$一下：$dp[i][a][b][c]$A person's ability to attribute value as$a,b,c$Can be up to the company$i$.

时间复杂度

$O(n\ast 400^3)$

可以优化的地方

• 1.Can be optimized into 3 d

• 2.语言选择 $C++(g++\mathrm{7.5.0})$,选$C++(clang++\mathrm{11.0.1})$就超时了.

• 3.In the middle of the fast power can first pretreatment can come out a little$log$.

代码：

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
//#define int long long
#define endl '\n'
using namespace std;


const int N = 2e5 + 10, MOD = 998244353;
int n, q, x, y, z;
int k1,k2,k3,k4;
bitset<402>fk[11][401][401];
inline int getid(int x,int y,int z){
    
    return 160801*(x)+(y)*(401)+z;
}
int getans(int iq, int eq, int aq){
    
    int ans=0;
    for(int i=1;i<=n;i++){
    
        ans+=fk[i][iq][eq][aq];
    }
    return ans;
}

int binpow(long long x, int y, int mod, long long res = 1){
    
    for (; y; y >>= 1, (x *= x) %= mod) if (y & 1) (res *= x) %= mod;
    return res;
}

int powq[2000010];

inline void solve(){
    
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
    
        cin >> k1;
        for(int j = 1; j <= k1; j++) {
    
            cin>>x>>y>>z;
            fk[i][x][y][z]=1;
        }
    } 
    
    for(short i=1;i<=n;i++){
    
        for(short j=1;j<=400;j++){
    
            for(short k=1;k<=400;k++){
    
                for(short x=1;x<=400;x++){
    
                    fk[i][j][k][x]=fk[i][j][k][x]|fk[i][j][k][x-1]|fk[i][j][k-1][x]|fk[i][j-1][k][x];
                }
            }
        }
    }
    int seed; cin >> seed;
    powq[0] = 1;
    for(int i = 1; i <= 2000000 + 5; i++){
    
        powq[i] = 1ll * powq[i - 1] * seed % MOD;
    }
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1, 400);
    int lastans = 0, ans = 0;
    for (int i = 1; i <= q; i++){
    
        int IQ = (u(rng) ^ lastans) % 400 + 1;  // The IQ of the i-th friend
        int EQ = (u(rng) ^ lastans) % 400 + 1;  // The EQ of the i-th friend
        int AQ = (u(rng) ^ lastans) % 400 + 1;  // The AQ of the i-th friend
        lastans = getans(IQ, EQ, AQ);           // The answer to the i-th friends
        (ans += (1ll * lastans * powq[q - i] % MOD)) %= MOD;
    }
    cout << (ans % MOD) << endl;
}

signed main(){
    
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1;
    while(t--) solve();
    return 0;
}