【题解】牛客IOI周赛17-提高组
相信大家在这次比赛中获得了很愉(zi)悦(bi)的体验。
T1
题意大致就是给出一棵白色边的树和一堆黑色边，要你求割掉一条白色边和一条黑色边，使得星星恰好被分成两部分的方案数。
这题就是题面太长了来恶心人的，但是善良的出题人已经把重点部分表明出来了，这个东西就可以直接对于黑边，用树上差分做了。
当割掉一条白边时，如果连接两边的黑边只有一条，那么就有一种方案，如果没有，那么断任意一条黑边都是可行的，否则，就没有方案。
当然也可以有更多其他的方法，log^2的也给过了。
T2
题意明显，发现有a,b<=1的数据点，选择打表找规律，发现%2Cans_0%3D0%2Cans_1%3D1)
。
然后继续找规律，发现*ans_%7Bi-1%7D%2Bb*ans%7Bi-2%7D%20(i%3E%3D2)%2Cans_0%3D0%2Cans_1%3D1)
，递推输出即可，考虑到大部分人都会矩阵优化，就没有把n开到更大。
教练，我不会找规律。
也是可做的，其实很多人都写了NTT，主要是依据这样的一条式子：
，把模数开到998244353也是为了误导大部分人写NTT。😁
那么你就可以获得60分的好成绩，加上数据里面有a=1,b=0这样简单的点，就可以获得70分的好成绩。
这样已经十分接近正解了，我们尝试用a,b,x将F表示出来：
Ans(x)是ans的母函数。
把它像f转换过来一样转换回去，就可以得到ans的递推式了。
教练，我不会生成函数。
如果你的数学学的足够好，其实可以直接脑子里面想一个这样的东西：
fi表示一步走i格的方案数是多少，那么其实可以看成一共走n格，每次可以走至少一步，那么会形成一个步数集合{a1,a2,...,ak}(a1+a2+...+ak=n)，那么使用这个步数集合的方案数就是
。
考虑ans的实际意义，我们可以考虑给当前最后一步扩长两格或者扩长一格，或者新增一步。
当你要扩长一格时，相当于从
中转移过来，因为扩长一格的方案数是a。
当你要扩长两格是，相当于从
中转移过来，因为扩长两个的方案数是b。
当你要新增一步时，相当于从
中转移过来，因为新增的一步只能从1格开始，为什么?
所以也可以得到答案的递推式。
T3
这次撞题不能责怪出题人，真的没有碰到过。
其实考虑补集转化后，只要求出一个交点和两个交点的组的方案数就可以了。
想想一格交点的是什么样子的？肯定是线段的两个端点，一个在三角形里面，一个在三角形外面，这个可以直接用bitset来做，统计一个向量逆时针方向的点集合，然后枚举一个三角形，算内部的点就是按位与，时间复杂度)
两个交点的怎么算？可以用(全部方案的交点数目-一个交点的方案数)/2，考虑对于一个四边形，对角线一定有一个交点，有2*(n-4)种方案形成三角形（任意加一个点，然后分别与对角线形成三角形，求四边形个数跟上面的方法类似。
减减就是答案。
