【THUWC2019模拟2019.1.18】Counting

(File IO): input:counting.in output:counting.out

Time Limits: 2000 ms Memory Limits: 1048576 KB Detailed Limits

Description

羽月最近發現，她發動能力的過程是這樣的：

建構一個 V 個點的有向圖 G，初始為沒有任何邊，接下來羽月在腦中建構出一個長度為 E 的邊的序列，序列中元素兩兩不同，然後羽月将這些邊依次加入圖中，每次加入之後計算目前圖的強連通分量個數并記下來，最後得到一個長度為E 的序列，這個序列就是能力的效果。

注意到，可能存在邊的序列不同而能力效果相同的情況，是以羽月想請你幫她計算能發動的不同能力個數，答案對 998244353 取模。你需要對于1<=E<=V*(V-1)的所有 E 計算答案。

Input

一行一個整數 V。

Output

一行 V*(V-1)個整數，用空格隔開，第 i 個整數表示 E=i 的答案。

Sample Input

4

Sample Output

1 2 4 9 20 39 64 89 114 114 114 114

【樣例說明】

資料中的 p 為 0.3

1×3×(0.3×0.3×0.7)+3×0.3×0.3×0.3=0.27

貢獻為 1 的情況有三種

貢獻為 3 的情況有一種

Data Constraint

對于 10%的資料，1<=V<=5

對于 30%的資料，1<=V<=20

對于 60%的資料，1<=V<=50

對于 100%的資料，1<=V<=100

感想

最近做了一道題目，感覺收獲挺大

1、題目要自己想，做題的時候幾次想點開題解，最後還是自己解決了問題，感覺不錯

2、遇到困難的時候要換一個角度，多從題目性質入手

3、端正心态，不要因為沒有去冬令營而灰心喪氣

題解

看到這道題先讀懂題意

發現這是讓我們求出可以構造出來的所有聯通分量的序列個數

乍一看無法入手，仔細想一想可以歸納一些繁雜的情況總結為一種情況來覆寫

考慮已經對于一種加邊方案來講，有哪些加邊的方法會得到不一樣的答案。

用數學歸納法：

我們可以在一個與目前塊不連通的地方增加一條邊，使得聯通塊的個數減少一。

然而你發現，這樣做似乎是與你從目前的聯通塊的最大編号的點往前連接配接所得到的方案會重複；假設之前塊中有p個強連通，那麼就可以相應的減少1~p個強連通分量。

或者，我們可以浪費一條邊

有兩種方式可以浪費：1、在前邊随便把兩個點連上又不改變聯通分量的數目

2、往後任意連一條邊

發現把前邊的任意兩個點連上可以轉換為把所有的邊都連完之後的随意連邊時間

是以浪費邊隻有往後任意連一條邊的情況

問題在與往後連哪一條邊

發現如果連的邊不是後邊的第一個點，可以将後邊的第一個點與後邊的任意一個點交換來替代。

是以隻會向後連一條邊

當然，對于第零條邊，肯定是聯通的。

這樣似乎就可以轉移了

設 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示為已經連了i條邊，有j個強連通分量，已經用了k個點的方案數

則有：

f [ i + 1 ] [ p ] [ k ] = f [ i + 1 ] [ p ] [ k ] + f [ i ] [ j ] [ k ] f [ i + 1 ] [ n ] [ k ] = f [ i + 1 ] [ n ] [ k ] + f [ i ] [ j ] [ k ] f [ i + 1 ] [ j + 1 ] [ k + 1 ] = f [ i + 1 ] [ j + 1 ] [ k + 1 ] + f [ i ] [ j ] [ k ] f[i+1][p][k]=f[i+1][p][k]+f[i][j][k]\\ f[i+1][n][k]=f[i+1][n][k]+f[i][j][k]\\ f[i+1][j+1][k+1]=f[i+1][j+1][k+1]+f[i][j][k] f[i+1][p][k]=f[i+1][p][k]+f[i][j][k]f[i+1][n][k]=f[i+1][n][k]+f[i][j][k]f[i+1][j+1][k+1]=f[i+1][j+1][k+1]+f[i][j][k]

最後判定會不會出現重邊，推一下發現如果 i > ( j − 1 ) ∗ ( j − 2 ) / 2 + ( k − j + 1 ) ∗ ( k − 1 ) i>(j-1)*(j-2)/2+(k-j+1)*(k-1) i>(j−1)∗(j−2)/2+(k−j+1)∗(k−1)的話，那麼說明就有了重邊。判掉就好了

代碼

#include<cstdio>
#define mod 998244353
#define N 103
#define M 10003
using namespace std;
int n;
long long f[M][N][N];
int main()
{
	freopen("counting.in","r",stdin);
	freopen("counting.out","w",stdout);
	scanf("%d",&n);
	f[0][1][1]=1;
	for (int i=0;i<=n*(n-1);i++)
	{
		for (int j=0;j<=n;j++)
			for (int k=0;k<=n;k++)
			{
				int pn=j+n-k;
				if (i>(k-j+1)*(k-1)+(j-1)*(j-2)/2) f[i][j][k]=0;
			}
		int j,k;j=k=1;
		for (int j=0;j<=n;j++)
		{
			for (int k=0;k<=n;k++)
			{
				if (f[i][j][k]==0) continue;
				f[i+1][j+1][k+1]=(f[i+1][j+1][k+1]+f[i][j][k]);
				if (f[i+1][j+1][k+1]>mod) f[i+1][j+1][k+1]-=mod;
			//	f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%mod;
				for (int p=1;p<j;p++)
				{
					f[i+1][p][k]=(f[i+1][p][k]+f[i][j][k]);
					if (f[i+1][p][k]>mod) f[i+1][p][k]-=mod;
				}
			}
			f[i+1][j][n]=(f[i+1][j][n]+f[i][j][n])%mod;
			if (f[i+1][j][n]>mod) f[i+1][j][n]-=mod;
		}
	}
	for (int i=1;i<=n*(n-1);i++)
	{
		long long ans=0;
		for (int j=1;j<=n;j++)
		{
			for (int k=0;k<=n;k++)
			{
				int pn=j+n-k;
				if (i<=(k-j+1)*(k-1)+(j-1)*(j-2)/2)
					ans=(ans+f[i][j][k])%mod;
			}
		}
		printf("%lld ",ans);
	}
}