8.13总结

刺骨的言语ヽ痛彻心扉 2023-08-17 15:35 40阅读 0赞

# 8.13总结 #

![1735240-20190814082108324-148383751.png][]

今天的比赛真是爽死了

三道计数题

## 得分 ##

30+20+10

Rank9

惨不忍睹

## T1 ##

![1735240-20190814082129339-1232603031.png][]

![1735240-20190814082141109-1908580533.png][]

### 正解 ###

![1735240-20190814082200609-1716231882.png][]

枚举A,枚举有几个元素值大于m-1来容斥。偶加奇减。

由于要固定几个元素大于m-1，所以从A里面减掉i\*(m-1)来钦定i个元素大于m-1。剩下的A随便分，再随便从k个里面选i个加上m-1来使它们大于m-1。

## T2 ##

![1735240-20190814082221951-1712093740.png][]  
![1735240-20190814082225415-1795988535.png][]

### 正解 ###

全部x都给出了，肯定有玄机。观察发现全部x的质因子次数最大为2。

每个质因子可以分开考虑。只要每个质因子在每一行每一列的乘积合法，总的矩阵也是合法的。思考发现，答案可以分为三个部分，即：符号的方案数\*一次质因子的方案数\*二次质因子的方案数。

符号的方案数即为\\(2^\{(n-1)^2\}\\)

一次质因子的方案数即为\\(n!\\)

二次质因子的方案数有点难算。设f\[i\]表示i\*i的矩形最后一列放了两个1的方案数，g\[i\]表示i\*i的矩形最后一列放了一个二的方案数。

\\(g\[i\]=(f\[i-1\]+g\[i-1\])\*i\\)

\\(f\[i\]=C\_i^2\*(2f\[i-1\]+g\[i-1\])\\)

这两条式子跟别人研究了很久也没搞懂。

## T3 ##

![1735240-20190814082255879-46057984.png][]  
![1735240-20190814082306284-68930082.png][]

### 正解 ###

我们发现，一个合法的序列一定对应一个前缀max序列。

![1735240-20190814082314697-1513041807.png][]

所以我们只要统计出有多少中合法的前缀max序列就能直接得到答案了

关键是怎么合法的前缀max序列要满足哪些条件。

![1735240-20190814082321178-887556010.png][]

对与y<x的情况与把y和x交换的情况是等价的。因为可以把那个排列的下标和权值交换，仍然是一个合法的序列。

![1735240-20190814082334290-1016102374.png][]

问题转化为求在一个平面直角坐标系上经过点(x,y)但不经过直线y=x-1的(1,1)到(n,n)的路径数量，直接用翻折法求即可。

转载于:https://www.cnblogs.com/leason-lyx/p/11349661.html

[1735240-20190814082108324-148383751.png]: /images/20230810/168af5d6b55549879eafd8c37523a7ad.png
[1735240-20190814082129339-1232603031.png]: /images/20230810/2974fcbe8c0845abab28bb97fa665d68.png
[1735240-20190814082141109-1908580533.png]: /images/20230810/051d4fd8075e45c9ba2d53fe27ffb968.png
[1735240-20190814082200609-1716231882.png]: /images/20230810/d9c38a86dfdf4dde9d02225a0d07e443.png
[1735240-20190814082221951-1712093740.png]: /images/20230810/9b0b5e3744924245a2b2192494f7957c.png
[1735240-20190814082225415-1795988535.png]: /images/20230810/383076c50b2540419f22536d59da0731.png
[1735240-20190814082255879-46057984.png]: /images/20230810/0d4800b5738f4b3b9de3d97898355ec3.png
[1735240-20190814082306284-68930082.png]: /images/20230810/5dc6e87c8e414e059d580a83eea614ba.png
[1735240-20190814082314697-1513041807.png]: /images/20230810/cbc52df55fbd42f296657c3ef727b25a.png
[1735240-20190814082321178-887556010.png]: /images/20230810/3ce61e263ce04e4b910b752a61e63822.png
[1735240-20190814082334290-1016102374.png]: /images/20230810/1dd3224f5d9a43a9867ead7b75372cf0.png