Submission #47385780

---

Source Code Expand

#include<iostream>
#include<map>
#include<cstring>
using namespace std;

const int MOD = 998244353;

long long n;
int x, y, z;
map<long long, map<long long, map<long long, long long>>> dp[70][12][12][12];

int get_gcd(int a, int b)
{
    int temp;
    
    while(a % b)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    
    return b;
}

int get_lcm(int a, int b)
{
    return a / get_gcd(a, b) * b;
}

long long recur(long long cur, int cbit, long long a, long long b, long long c)
{
    long long ret = 0;
    long long da, db, dc;
    
    if(a > n || b > n || c > n) return 0;
    if(cur == 0) return a % x == 0 && b % y == 0 && c % z == 0;
    
    da = min(n - a, 2 * cur - 1);
    db = min(n - b, 2 * cur - 1);
    dc = min(n - c, 2 * cur - 1);
    
    if(dp[cbit][a % x][b % y][c % z][da][db].find(dc) != dp[cbit][a % x][b % y][c % z][da][db].end()) return dp[cbit][a % x][b % y][c % z][da][db][dc];
        
    ret += recur(cur >> 1, cbit - 1, a + cur, b, c + cur);
    ret += recur(cur >> 1, cbit - 1, a, b + cur, c + cur);
    ret += recur(cur >> 1, cbit - 1, a + cur, b + cur, c);
    ret += recur(cur >> 1, cbit - 1, a, b, c);
        
    return dp[cbit][a % x][b % y][c % z][da][db][dc] = ret % MOD;
}

int main()
{
    long long ans;
    
    cin >> n >> x >> y >> z;
    
    ans = recur(1LL << 61, 61, 0, 0, 0);
    
    ans += MOD;
    ans -= (n / get_lcm(x, y)) % MOD;
    
    ans += MOD;
    ans -= (n / get_lcm(y, z)) % MOD;
    
    ans += MOD;
    ans -= (n / get_lcm(x, z)) % MOD;
    
    ans += MOD;
    ans--;
    
    cout << ans % MOD;
}

Submission Info

Judge Result