Submission #71903667

---

Source Code Expand

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
using namespace std;
const int N = 507, mod = 998244353;
struct mint {
	int x;
	inline mint(int o = 0) { x = o; }
	inline mint & operator = (int o) { return x = o, *this; }
	inline mint & operator += (mint o) { return (x += o.x) >= mod && (x -= mod), *this; }
	inline mint & operator -= (mint o) { return (x -= o.x) < 0 && (x += mod), *this; }
	inline mint & operator *= (mint o) { return x = (ll) x * o.x % mod, *this; }
	inline mint & operator ^= (int b) {
		mint w = *this;
		mint ret(1);
		for(; b; b >>= 1, w *= w) if(b & 1) ret *= w;
		return x = ret.x, *this;
	}
	inline mint & operator /= (mint o) { return *this *= (o ^= (mod - 2)); }
	friend inline mint operator + (mint a, mint b) { return a += b; }
	friend inline mint operator - (mint a, mint b) { return a -= b; }
	friend inline mint operator * (mint a, mint b) { return a *= b; }
	friend inline mint operator / (mint a, mint b) { return a /= b; }
	friend inline mint operator ^ (mint a, int b) { return a ^= b; }
};
inline mint qpow(mint x, int y = mod - 2) { return x ^ y; }
mint fac[N], ifac[N], inv[N];
void init(int x) {
	fac[0] = ifac[0] = inv[1] = 1;
	L(i, 2, x) inv[i] = (mod - mod / i) * inv[mod % i];
	L(i, 1, x) fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * inv[i];
} 
mint C(int x, int y) {
	return x < y || y < 0 ? 0 : fac[x] * ifac[y] * ifac[x - y];
}
inline mint sgn(int x) {
	return (x & 1) ? mod - 1 : 1;
}

int n, m, k;
int a[N], b[N];

struct Mat {
    int M[4][4];
    Mat(int x = 0) {
        me(M, 0);
        L(i, 0, 3) M[i][i] = x;
    }
};
Mat operator * (Mat A, Mat B) {
    Mat C;
    L(i, 0, 3) L(j, 0, 3) L(k, 0, 3) {
        (C.M[i][j] += (ll) A.M[i][k] * B.M[k][j] % mod) %= mod;
    }
    return C;
}
Mat operator + (Mat A, Mat B) {
    Mat C;
    L(i, 0, 3) L(j, i, 3) {
        C.M[i][j] = (A.M[i][j] + B.M[i][j]) % mod;
    }
    return C;
}
Mat operator ^ (Mat A, int b) {
    Mat ret(1);
    for(; b; b >>= 1, A = A * A) if(b & 1) ret = ret * A;
    return ret;
}

void Main() {
}
mint dp[N];
mint calc(int n, int x, int y, int z) {
    //L(i, 0, n) dp[i] = 0;
    Mat C(0);
    int v[3] = {x, y, z};
    L(i, 0, 2) L(j, 0, i) C.M[j][i] = v[i];
    Mat ans = (C ^ n);
    return ((ll)ans.M[0][0] + ans.M[0][1] + ans.M[0][2]) % mod;
}
int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    // u, v, v <= u
    mint ans = 0;
    L(u, 1, min(k, m)) {
        L(v, 1, min(u, (k - 1) / u)) {
            int lim = min(k - u * v, m);
            int ls = min(v, lim);
            // (<v) u, (<v) v, (<=ls), [<=lim]
            ans += calc(n - 3, v - 1, v - 1, ls) * lim;
        }
    }
    // v, u, v<u
    L(u, 1, min(k, m)) {
        L(v, 1, min(u - 1, (k - 1) / u)) {
            int lim = min(k - u * v, m);
            int ls = min(v, lim);
            // (<v) v, (<=min(v,u-1)) u, (<=ls), [<=lim]
            ans += calc(n - 3, v - 1, min(v, u - 1), ls) * lim;
        }
    }
    cout << ans.x << '\n';
    return 0;
} 

Submission Info

Judge Result