Wannafly Camp 2020 Day 1C 染色图 - 组合数学,整除分块

定义一张无向图 G=⟨V,E⟩ 是 k 可染色的当且仅当存在函数 f:V↦{1,2,⋯,k} 满足对于 G 中的任何一条边 (u,v)，都有 f(u)≠f(v)。

定义函数 g(n,k) 的值为所有包含 n 个点的无自环、无重边的 k 可染色无向图中的边数最大值。举例来说，g(3,1)=0,g(3,2)=2,g(3,3)=3。

现在给出三个整数 n,l,r，你需要求解：(\sum_{i=l}^rg(n,i))mod998244354

Solution

把 \(n\) 个点分成 \(m\) 份，尽可能均分，方案是显然的。每一份之间不连边，不同份之间都连上，边数相当于一个大完全图减去一堆小完全图，推出单个后考虑求和，整除分块即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

int M(int x) {

    return (x%mod+mod)%mod;

}

int calc(int n,int m,int s) {

    int l=s,r,ans=0;

    while(l<=m) {

        r=n/l?min(n/(n/l),m):m;

        ans+=M(M(n*(n-1)/2)*(r-l+1));

        ans-=M(M(n*(n/l))*(r-l+1));

        ans+=M(M((n/l)*(n/l+1)/2)*M((r-l+1)*(l+r)/2));

        ans=M(ans);

        l=r+1;

    }

    return ans;

}

signed main() {

    ios::sync_with_stdio(false);

    int T,n,l,r,ans;

    cin>>T;

    while(T--) {

        cin>>n>>l>>r;

        ans=0;

        cout<<calc(n,r,l)<<endl;

    }

}

巴特西

Wannafly Camp 2020 Day 1C 染色图 - 组合数学,整除分块

Solution

最新文章

热门文章