問題1：グリッド経路の組み合わせと寄与計算

本問はグリッド上の経路数と各初期値が最終結果に与える寄与度を計算する問題です。始点から終点 $(N, M)$ への移動において、右と上のみ移動可能と仮定します。各地点 $(i, j)$ から $(N, M)$ への移動経路の総数は、右への移動回数と上への移動回数の組み合わせにより $\frac{(N-i + M-j)!}{(N-i)! (M-j)!}$ で求められます。

各初期値の寄与は、この経路数と対応する重みの累乗の積として計算できます。階乗、階乗の逆元、および重みの累乗を事前計算（前処理）しておくことで、全体の計算量を $O(N + M)$ に抑え、効率的に答えを求めることが可能です。

#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 998244353;

long long modpow(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modinv(long long n) {
    return modpow(n, MOD - 2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int rows, cols;
    long long weightR, weightC;
    cin >> rows >> cols >> weightR >> weightC;

    weightR %= MOD;
    weightC %= MOD;

    vector<long long> initR(rows + 1), initC(cols + 1);
    for (int i = 1; i <= rows; ++i) { cin >> initR[i]; initR[i] %= MOD; }
    for (int i = 1; i <= cols; ++i) { cin >> initC[i]; initC[i] %= MOD; }

    int maxN = rows + cols + 5;
    vector<long long> fact(maxN), invFact(maxN), powR(maxN), powC(maxN);

    fact[0] = invFact[0] = powR[0] = powC[0] = 1;
    for (int i = 1; i < maxN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        powR[i] = (powR[i - 1] * weightR) % MOD;
        powC[i] = (powC[i - 1] * weightC) % MOD;
    }
    invFact[maxN - 1] = modinv(fact[maxN - 1]);
    for (int i = maxN - 2; i >= 1; --i) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }

    auto nCr = [&](int n, int r) -> long long {
        if (r < 0 || r > n) return 0;
        return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
    };

    long long totalAns = 0;

    for (int i = 1; i <= rows; ++i) {
        int distR = rows - i;
        int distC = cols - 1;
        long long paths = nCr(distR + distC, distR);
        long long contrib = paths * powC[distR] % MOD * powR[distC] % MOD * initR[i] % MOD;
        totalAns = (totalAns + contrib) % MOD;
    }

    for (int j = 1; j <= cols; ++j) {
        int distR = rows - 1;
        int distC = cols - j;
        long long paths = nCr(distR + distC, distR);
        long long contrib = paths * powC[distR] % MOD * powR[distC] % MOD * initC[j] % MOD;
        totalAns = (totalAns + contrib) % MOD;
    }

    cout << totalAns << "\n";
    return 0;
}

問題2：基環木における独立集合の最小コスト

この問題は基環木（サイクルを1つだけ含む連結グラフ）上の頂点選択問題です。与えられたグラフは基環木としてモデル化でき、木DP（動的計画法）の拡張によって解くことができます。

基環木は通常の木より辺が1つ多いため、まず深さ優先探索（DFS）を用いてサイクルを構成する辺を1つ特定し、その辺を仮想的に切断して木構造に変換します。その後、切断した辺の両端の頂点について、片方を「必ず選択する」という制約を設けた上で木DPを実行します。各頂点について「選択する場合」と「選択しない場合」の最小コストをボトムアップで計算し、最終的な最適解を導出します。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;
int cycleU = -1, cycleV = -1;
vector<bool> visited;

void findCycle(int u, int parent, const vector<vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (visited[v]) {
            if (cycleU == -1) {
                cycleU = u;
                cycleV = v;
            }
            return;
        }
        findCycle(v, u, adj);
        if (cycleU != -1) return;
    }
}

void treeDP(int u, int parent, const vector<vector<int>>& adj, const vector<long long>& cost, vector<vector<long long>>& dp) {
    dp[u][1] = cost[u];
    dp[u][0] = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if ((u == cycleU && v == cycleV) || (u == cycleV && v == cycleU)) continue;
        
        treeDP(v, u, adj, cost, dp);
        dp[u][1] += min(dp[v][0], dp[v][1]);
        dp[u][0] += dp[v][1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long costType1, costType2;
    cin >> n >> costType1 >> costType2;

    vector<long long> nodeCost(n + 1, 0);
    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        nodeCost[u] += costType1;
        nodeCost[v] += costType2;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    visited.assign(n + 1, false);
    findCycle(1, 0, adj);

    vector<vector<long long>> dp(n + 1, vector<long long>(2, 0));
    
    treeDP(cycleU, cycleV, adj, nodeCost, dp);
    long long ans1 = dp[cycleU][1]; 

    dp.assign(n + 1, vector<long long>(2, 0));
    treeDP(cycleV, cycleU, adj, nodeCost, dp);
    long long ans2 = dp[cycleV][1];

    cout << min(ans1, ans2) << "\n";
    return 0;
}

問題3：約数の個数と完全平方数に基づく数論計算

本問は約数の個数のパリティ（奇偶性）を利用した数論の問題です。$(-1)^{d(i \times j)}$ の値は、約数の個数 $d(i \times j)$ が奇数のときのみ $-1$ となり、偶数のときは $1$ になります。約数の個数が奇数になるのは、対象の数が完全平方数である場合に限定されます。

したがって、$i \times j$ が完全平方数となる条件を考察します。任意の整数 $i$ は $p \times q^2$（$p$ は平方因子を持たない無平方数）と一意に分解できます。このとき、$i \times j$ が完全平方数となるためには、$j$ も $p \times r^2$ の形である必要があります。条件を満たす $j$ の個数は $\lfloor\sqrt{M / p}\rfloor$ となります。各 $i$ に対する無平方部分 $p$ の値は、線形篩（エラトステネスの篩の拡張）の要領で $O(N)$ かけて前計算できます。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int limitN, limitM;
    cin >> limitN >> limitM;

    vector<int> squareFreePart(limitN + 1, 0);
    vector<bool> isComposite(limitN + 1, false);
    vector<int> primes;

    squareFreePart[1] = 1;
    for (int i = 2; i <= limitN; ++i) {
        if (!isComposite[i]) {
            primes.push_back(i);
            squareFreePart[i] = i;
        }
        for (int p : primes) {
            long long nextVal = (long long)i * p;
            if (nextVal > limitN) break;
            isComposite[nextVal] = true;
            if (i % p == 0) {
                squareFreePart[nextVal] = squareFreePart[i];
                break;
            } else {
                squareFreePart[nextVal] = squareFreePart[i] * p;
            }
        }
    }

    long long totalSum = 0;
    for (int i = 1; i <= limitN; ++i) {
        int p = squareFreePart[i];
        long long maxR = sqrt((double)limitM / p);
        if (maxR % 2 == 1) {
            totalSum--;
        } else {
            totalSum++;
        }
    }

    cout << totalSum << "\n";
    return 0;
}