QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#667681#5586. Digits of Unityenze114514AC ✓458ms245260kbC++203.6kb2024-10-23 02:13:572024-10-23 02:13:57

Judging History

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

  • [2024-10-23 02:13:57]
  • 评测
  • 测评结果:AC
  • 用时:458ms
  • 内存:245260kb
  • [2024-10-23 02:13:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

const ld pi = 3.14159265358979323846;
const ll INF = 1e18;
const int mod = 998244353;

template <typename T>
struct Z{
    static const T Mod = (T)998244353;
    T num;

    Z() : num(0) {}

    Z(T n) : num(n % Mod) {
        if (num < 0) num += Mod;
    }

    Z operator+(const Z& other) const{
        T res = num + other.num;
        if(res >= Mod) res -= Mod;
        return Z(res);
    }

    Z operator-(const Z& other) const{
        T res = num - other.num;
        if(res < 0) res += Mod;
        return Z(res);
    }

    Z operator*(const Z& other) const{
        return Z((ll)num * other.num);
    }

    Z operator/(const Z& other) const{
        return (*this) * other.inverse();
    }

    Z pow(long long power) const{
        Z res(1);
        Z base(num);
        long long exp = power;
        while(exp > 0){
            if(exp & 1){
                res = res * base;
            }
            base = base * base;
            exp >>=1;
        }
        return res;
    }

    Z inverse() const{
        return pow(Mod - 2);
    }

    friend ostream& operator<<(ostream& os, const Z& z){
        os << z.num;
        return os;
    }
};

template <typename T>
struct Binom {
public:
    vector<Z<T>> fact;      
    vector<Z<T>> inv_fact;   

    Binom(int n) : fact(n + 1, Z<T>(1)), inv_fact(n + 1, Z<T>(1)) {
        for(int i =1; i <=n; i++){
            fact[i] = fact[i-1] * Z<T>(i);
        }
        inv_fact[n] = fact[n].inverse();
        for(int i = n-1; i >=0; i--){
            inv_fact[i] = inv_fact[i+1] * Z<T>(i+1);
        }
    }

   
    Z<T> comb(int n_val, int k_val) const{
        if(n_val < 0 || k_val < 0 || n_val < k_val){
            return Z<T>(0);
        }
        return fact[n_val] * inv_fact[k_val] * inv_fact[n_val - k_val];
    }

   
    Z<T> perm(int n_val, int k_val) const{
        if(n_val < k_val || k_val < 0){
            return Z<T>(0);
        }
        return fact[n_val] * inv_fact[n_val - k_val];
    }
};

void fast_zeta_transform(vector<int> &f, int B){
    for(int i=0; i < B; i++){
        for(int mask = 0; mask < (1 << B); mask++){
            if((mask & (1 << i)) ==0 ){
                f[mask] += f[mask | (1 << i)];
            }
        }
    }
}

void mobius_inversion(vector<Z<ll>> &g, int B){
    for(int i = 0; i < B; i++){
        for(int mask = 0; mask < (1 << B); mask++){
            if((mask & (1 << i)) ==0 ){
                g[mask] = g[mask] - g[mask | (1 << i)];
            }
        }
    }
}

void solve() {
    int n, k;
    ll m;
    cin >> n >> k >> m;

    int B = 0;
    while((1LL << B) <= m){
        B++;
    }
    B = max(B, 1);  

    int size = 1 << B;

    vector<int> f(size, 0);
    for(ll x = 1; x <= m; x++){
        f[x] += 1;
    }


    fast_zeta_transform(f, B);

    Binom<ll> binom(m); 
 
    vector<Z<ll>> P(size, Z<ll>(0));
    for(int c=0; c < size; c++){
        if(f[c] >= n){
            P[c] = binom.perm(f[c], n);
        }
    }

    vector<Z<ll>> g = P;  
    mobius_inversion(g, B);
 
    Z<ll> answer = 0;
    for(int c=0; c < size; c++){
        if(__builtin_popcount(c) >=k){
            answer = answer + g[c];
        }
    }
    cout << answer << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while(t--){
        solve();
    }
    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3824kb

input:

2 2 10

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

3 4 14

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 7240kb

input:

2 1 100000

output:

910073387

result:

ok single line: '910073387'

Test #4:

score: 0
Accepted
time: 14ms
memory: 10496kb

input:

30 6 136665

output:

552360422

result:

ok single line: '552360422'

Test #5:

score: 0
Accepted
time: 0ms
memory: 5152kb

input:

178 6 51500

output:

788418998

result:

ok single line: '788418998'

Test #6:

score: 0
Accepted
time: 7ms
memory: 7000kb

input:

445 4 91471

output:

322733059

result:

ok single line: '322733059'

Test #7:

score: 0
Accepted
time: 28ms
memory: 17952kb

input:

23634 10 299334

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 19ms
memory: 17972kb

input:

242554 5 287650

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

1 3 7

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

1 1 7

output:

7

result:

ok single line: '7'

Test #12:

score: 0
Accepted
time: 441ms
memory: 245260kb

input:

500000 500000 5000000

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 439ms
memory: 245100kb

input:

250000 1 5000000

output:

578914111

result:

ok single line: '578914111'

Test #14:

score: 0
Accepted
time: 25ms
memory: 20312kb

input:

4096 6 449389

output:

129538870

result:

ok single line: '129538870'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

50 2 50

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 445ms
memory: 245184kb

input:

250000 65 5000000

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 458ms
memory: 245192kb

input:

1 1 5000000

output:

5000000

result:

ok single line: '5000000'

Test #18:

score: 0
Accepted
time: 458ms
memory: 244968kb

input:

2 17 5000000

output:

7104108

result:

ok single line: '7104108'