AT_arc212_a [ARC212A] Four TSP题解

zpy12345 · 2026-04-21 16:44:55 · 题解

突然意识到再不写题解估值就要掉没了。

依旧安利博客。

思路

容易发现符合题意的哈密顿环只有以下三种情况。 ::::info[防止图片影响观感] :::: 于是我们可以枚举每一条边的值，判断是三种情况中的哪一个，时间复杂度 O(K^6)。

这样的复杂度显然无法接受，不过我们发现，边 \left ( 1,2 \right ) 与 \left ( 3,4 \right ) 一定是同时存在于哈密顿环中/都不在哈密顿环中，边 \left ( 1,4 \right ) 与 \left ( 2,3 \right ) 、边 \left ( 1,3 \right ) 与 \left ( 2,4 \right ) 同理。于是我们可以直接枚举边 \left ( 1,2 \right ) 与 \left ( 3,4 \right ) 的边权和、边 \left ( 1,4 \right ) 与 \left ( 2,3 \right ) 的边权和、边 \left ( 1,3 \right ) 与 \left ( 2,4 \right ) 的边权和，判断是三种情况的哪一种，然后乘上相应分配的方案数即可。时间复杂度 O(K^2)（显然只要知道两组边的边权和，第三组边的边权和就可以求出了）。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int k;
int main()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>k;
    int ans=0;
    for(int i=2;i<=k;i++)
        for(int j=2;i+j<=k;j++)
        {
            int p=k-i-j;
            if(p<2) continue ;
            int sum1=i+j,sum2=i+p,sum3=j+p;
            ans+=(p-1)*1ll*(j-1)%mod*(i-1)%mod*min(sum1,min(sum2,sum3))%mod;
            ans%=mod;
        }
    cout<<ans;
    return 0;
}