QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#667681 | #5586. Digits of Unity | enze114514 | AC ✓ | 458ms | 245260kb | C++20 | 3.6kb | 2024-10-23 02:13:57 | 2024-10-23 02:13:57 |
Judging History
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'