2019.9.11

In this pathetic day of US , all the sorrow could be taken down.

P1329 数列

题目描述

有这样一种数列A_{1}A1、A_{2}A2、A_{3}A3、……A_{n}A**n,其中A_{1}=0A1=0,且对任意一项A_{i}A**i满足|A_{i}-A_{i+1}|=1∣A**iA**i+1∣=1(1\le i<n1≤i<n)。设S=A_{1}+A_{2}+A_{3}+…+A_{n}S=A1+A2+A3+…+A**n,表示前nn项之和。 现在给出数列长度nn与数列前nn项之和SS,要求:

输出满足条件的数列的总数。

输出满足条件的100100个数列(如果不满100100个就全部输出)。

输入格式

一行,包含两个整数nn和SS(1\le n\le 1001≤n≤100),用一个空格隔开。

输出格式

第1行一个整数t(0\le t\le 2^{63}-10≤t≤263−1),表示满足条件的数列总数。

接下来每行输出一个数列,数列各项之间用一个空格隔开。

若满足条件的数列数目不满100100个,全部输出即可。

输入输出样例

输入 #1复制

输出 #1复制

题解

有个标签是数论我觉得是扯淡,我感觉这道题线性dp再好不过了。

首先设$f_{i,j,k}$表示前$i$个数最后一个数是$j$并且加和为$k$的方案数是多少,最后的答案是$\sum_{i=-n}^{n}f_{n,i,S}$

不难发现状态包含了全部需要转移的信息。每次转移是常数复杂度,只能比前一个多-1,1。

时间复杂度是$O(n^4)$

这个输出方案很不好办,可能需要贪心。

用另外一个数组zz[i,j,k,1]表示f[i-1,j-1,k-j]是否存在方案,存在即保存j-1,意为可以从j-1得到当前的状态,zz[i,j,k,2]保存f[i-1,j+1,k-j]是否存在方案。

最后,用递归输出就行了

很套路的做法,还是一样递归输出路径


现在开始爆肝CTS和WC的难题了。


[国家集训队]礼物

题目描述

一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物,当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同,在小E心中分量越重的人,收到的礼物会越多。小E从商店中购买了n件礼物,打算送给m个人,其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数(两个方案被认为是不同的,当且仅当存在某个人在这两种方案中收到的礼物不同)。由于方案数可能会很大,你只需要输出模P后的结果。

输入格式

输入的第一行包含一个正整数P,表示模;

第二行包含两个整整数n和m,分别表示小E从商店购买的礼物数和接受礼物的人数;

以下m行每行仅包含一个正整数wi,表示小E要送给第i个人的礼物数量。

输出格式

若不存在可行方案,则输出“Impossible”,否则输出一个整数,表示模P后的方案数。

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

输出 #2复制

说明/提示

【样例说明】

下面是对样例1的说明。

以“/”分割,“/”前后分别表示送给第一个人和第二个人的礼物编号。12种方案详情如下:

1/23 1/24 1/34

2/13 2/14 2/34

3/12 3/14 3/24

4/12 4/13 4/23

设P=p1^c1 p2^c2 p3^c3 pt ^ ct,pi为质数。

对于15%的数据,n≤15,m≤5,pi^ci≤10^5;

在剩下的85%数据中,约有60%的数据满足t≤2,ci=1,pi≤10^5,约有30%的数据满足pi≤200。

对于100%的数据,1≤n≤10^9,1≤m≤5,1≤pi^ci≤10^5,1≤P≤10^9。

题解

这道题充分体现了我现在组合数学跟hape一样。

首先凭借感觉想到答案:

$ANS = \binom{n}{\sum w_i} * \prod _{j}\binom{\sum w_i - \sum w_{j-1}}{w_j}$

证明一一映射即可。

首先这种表达的每种方案肯定是正确的,证明所有正确的答案都被这种表达囊括即可。

考虑一种方案,选了$\sum w_i$个位置,这在答案的第一项体现,之后内部的分配再通过后面来包括。

然后扩展Lucas算法即可。