T2

2017-08-05

layout: post title: Luogu月赛T2 category : Intro tags : [tag1] —

洛谷月赛T2

题目描述

求 nn 个点的无向完全图删去一条边之后圈的个数，答案模 998244353998244353。

注：圈指的是任选一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径。

输入输出格式

输入格式： 第一行一个整数 TT，表示数据组数。

接下来 TT 行，每行一个整数 nn，意义如描述所述。

输出格式： 一共 TT 行，每行一个整数，表示答案。

思路

这个题显然是有规律的啦….虽然我的方法并不是很好

首先我们来看看

对于5去掉一条边，我们能够发现，这是一个四个点的完全图加上一个点引出三

条边

那么，四个点的完全图有的环，这个图也一定有；而这个图比4点完全图多出来

的环，一定要经过第五个点（红的那个）。

为了形成环，肯定是一边进，一边出，选择有C(3,2)种对于，而任意一种选择，

肯定落在两个点上，所以我们还要知道四个点的完全图，从A开始到B有几种方案

可以发现数出来，是5

用it[i]，表示i个点的完全图，任取A、B，A->B的方案数有多少

last[i]，表示i个点的完全图，有多少个环

那么 ans[n]=c(n-2,2)*it[n-1]+last[n-1]

到这里，60%已经可以解决了

接下来是AC

用计算器可以发现一个事情，剩下的40%只有100W的范围

所以…我们可以预（打）处（表）理一下

然后…就可以A了…

代码

#include<iostream>
#include<cstdio>
#define mod 998244353
#define M 999000000-2
#define ll long long
using namespace std;
ll T,n;
ll c[100021],it[100021];
ll last[100021];
void get_c()
{
    c[2]=1;
    for(ll i=3;i<=100020;i++)
    {
        c[i]=(i-1)*i/2;
        c[i]%=mod;
    }
    it[3]=2;
    for(ll i=4;i<=100020;++i)
    {
        it[i]=it[i-1]*(i-2)+1;
        it[i]%=mod;
    }
    last[3]=1;
    for(ll i=4;i<=100020;++i)
    {
        last[i]=c[i-1]*it[i-1]+last[i-1];
        last[i]%=mod;
    }
}
ll cb[1000010],lastb[1000010],itb[1000010];
void get_b()
{
	cb[0]=1420232,lastb[0]=876466444,itb[0]=141309211;
	ll to=1000005;
	for(ll i=1;i<=1000005;++i)
	{
		ll num=i+M;
		cb[i]=cb[i-1]+num-1;
		cb[i]%=mod;
		lastb[i]=cb[i-1]*itb[i-1]+lastb[i-1];
		lastb[i]%=mod;
		itb[i]=itb[i-1]*(num-2)+1;
		itb[i]%=mod;
	}
}
int main()
{
	scanf("%lld",&T);
	get_c();
	get_b();
	while(T--)
	{
		scanf("%lld",&n);
		if(n>M)
		{
			n%=M;
			ll ans=cb[n-2]*itb[n-1]+lastb[n-1];
			ans%=mod;
			printf("%lld\n",ans);
			continue;
		}
		ll ans=c[n-2]*it[n-1]+last[n-1];
		ans%=mod;
		printf("%lld\n",ans);
	}
}
Comment Box
(update the code to your comment plugin in comment-full.html)