从最近几次的考试题里面放几道上来好了

最近的NOIP赛的题目比较水，但是我为毛总是不想写对拍= =，所以一直没拉开分差，也没有AK过。

唯一在考场上面没想出来的是一道搜索题：就是要搞一个多维背包。考试的时候就觉得不可做，于是觉得应该是要搜索，但是总感觉维数大小是50会挂，而且这种题目让人感觉贪心可以骗些分的样子，我这种逗了一B的代码能力也就随便写了个贪心。最后题解里面说是要加一堆的优化：主要是物品的大小有很多重复的，这些就需要决策单调性，而且还有个边界判断后面还有没有解。虽然感觉还是很不科学，但是确实是能过的= =

补：10号也考了一场。duyege差点AK但是第三题我并没有想出来，想想当时的状态虽然一直在想但是很快就走神了，而且当时我也不知为何没有那么强的做出这道题的欲望。（我为毛这么萎啊！）后来看式子的时候也是感觉得了智商癌，一直没看懂。

题意：给定数组B，第i位代表A数组前i位有多少个小于等于i的数，求有多少个满足条件的A数组，并且A数组是一个1-n的排列。

题解：“很简单啊！”。当b[i]-b[i-1]=1时说明要不就是第i位有一个1-i之间的数，要不就是第1-i-1位有一个i，所以答案乘以2*(i-1-b[i-1])+1；当b[i]-b[i-1]=2时说明第i位有一个1-i-1之间的数，并且第1-i-1位有一个i，所以答案乘以(i-1-b[i-1])^2。回想我的思路我一直觉得如果设前i位有多少种方案是会有问题的，于是一直没往这方面想，现在想想真是SB。

还有一些NOI的模拟赛，有的题目如果放到NOIP的模拟赛中我是可以想出来的，但是我总是觉得这些题会很神，所以就没认真去想。而且这两天的状态是真心萎废，甚至考试中可以做到一道题调一个上午。感觉还是心态问题，考的人里面还有某爷、某司机什么的，总觉得自己完全不可能在这些人中间考好，完全没有进入考试状态，而且总是很容易就弃疗了。但是实力不会等于成绩啊，我有几次还是有考好的机会的，而且我完全不能是因为为了考好而考试，有的题目做起来本身就应该是愉快的啊。

不多说了还是放题目吧：就是有一个数列的第一项v0给出来了，然后有s1项每一项是前一项+1，还有s2项每一项是前一位的2倍，然后后面就是ai=ai-1*……ai-k，k<=101,N<=1e9，要求数列第N项对1e8+7取模。

题解：这东西肯定没办法直接搞，所以要想办法让递推式能用矩阵乘法优化。所以想到用让ai取log然后就可以用矩阵乘法搞了，但是由于取过了log所以没办法取模，肯定会有太大了，而且还会有精度问题，算它的幂，所以要想办法尽量不用log。而且矩阵乘法的递推矩阵是没有实数的，所以我们没必要取log，只要将递推矩阵快速幂之后的最后一次矩阵乘法化乘法为幂运算就可以了，由于最后一次是幂运算，而且用于取模的数是素数，所以在矩阵快速幂的时候就可以用费马小定理模P-1。感觉就是一堆东西杂在一起，并不算难。然后被细节坑到了30分，体会到了不写对拍的快感。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 205
#define M 100000007
#define eps 1e-9
#define ll long long
struct Matrix
 {
 	ll a[N][N];
 } emp,E,ans;
ll v0,s1,s2,m,n,t;
inline ll Quick_mi(ll x,ll y)
 {
 	ll z=1;
 	while (y)
 	 {
 	 	if (y&1) z=(z*x)%M;
 	 	x=(x*x)%M;
 	 	y/=2;
 	 }
 	return z;
 }
inline Matrix* Multi(Matrix *x,Matrix *y)
 {
 	Matrix *z=(Matrix*)(malloc(sizeof(Matrix)));
 	*z=emp;
 	for (int i=1;i<=m;i++)
 	 for (int j=1;j<=m;j++)
 	  for (int k=1;k<=m;k++)
 	    z->a[i][k]+=x->a[i][j]*y->a[j][k];
 	for (int i=1;i<=m;i++)
 	 for (int j=1;j<=m;j++)
 	   z->a[i][j]%=M-1;
 	return z;
 }
inline Matrix* Quick_mi(Matrix *x,ll y)
 {
 	Matrix *z;
 	z=(Matrix*)(malloc(sizeof(Matrix)));
 	*z=E;
 	while (y)
 	 {
 	 	if (y&1) z=Multi(z,x);
 	 	x=Multi(x,x);
 	 	y/=2;
 	 }
 	return z;
 }
int main()
 {
 	int i,j;Matrix q,w,*e;ll k,l;double o,p;
 	scanf("%d",&t);
 	while (t--)
 	 {
 	    memset(emp.a,0,sizeof(emp.a));memset(E.a,0,sizeof(E.a));
 	    memset(q.a,0,sizeof(q.a));memset(ans.a,0,sizeof(ans.a));
 	    memset(w.a,0,sizeof(w.a));
 	 	scanf("%d%d%d%d%d",&v0,&s1,&s2,&m,&n);
 	 	for (i=1;i<=m;i++)
 	 	  E.a[i][i]=1;
 	 	for (i=1;i<=m;i++)
 	 	  w.a[i][i-1]=w.a[i][m]=1;
 	 	for (i=1;i<=m;i++)
 	 	 for (j=1;j<=m;j++)
 	 	   ans.a[i][j]=1;
 	 	if (n<=s1+1)
 	 	  {cout <<v0+(n-1)<<endl;continue;}
 	 	k=v0+s1;
 	 	if (n<=s2+s1+1)
 	 	  {cout <<(k*Quick_mi(2,n-s1-1))%M<<endl;continue;}
 	 	if (m==s2+s1+1)
 	 	 {
 	 	 	q.a[1][1]=v0;
 	 	 	for (i=s1+1;i>=2;i--)
 	 	 	  q.a[1][i]=k--;
 	 	 	k+=s1;
 	 	 	for (i=m-s2+1;i<=m;i++)
 	 	 	  q.a[1][i]=(k=(k*2)%M);
 	 	 }else
 	 	if (m<=s2)
 	 	 {
 	 	 	k=(k*Quick_mi(2,s2-m))%M;
 	 	 	for (i=1;i<=m;i++)
 	 	 	  k=(k*2)%M,q.a[1][i]=k;
 	 	 }else
 	 	 {
 	 	 	for (i=m-s2;i>=1;i--)
 	 	 	  q.a[1][i]=k--;
 	 	 	k+=m-s2;
 	 	 	for (i=m-s2+1;i<=m;i++)
 	 	 	  q.a[1][i]=(k=(k << 1)%M);
 	 	 }
 	 	e=Quick_mi(&w,n-s2-s1-1);
 	 	for (i=1;i<=m;i++)
 	 	 for (j=1;j<=m;j++)
 	 	   ans.a[1][j]=(ans.a[1][j]*Quick_mi(q.a[1][i],e->a[i][j]))%M;
 	 	printf("%d\n",(int)(ans.a[1][m]%M));
 	 }
 	return 0;
 }

有道题由于第一题看错题一直觉得是FFT于是试着在考场上搞出FFT，所以没怎么想第三题，后来发现确实不难= =。

题意：有一个字符串，一开始只有大写字母，然后可以往中间加下划线、交换任意两个字符或者删字符。要求最终串的长度为N，任意两个相同的字母之间有至少k个比它大的字符（设下划线的ASCII码最大）。

题解：可以字母从小到大搞，设a[i][j]为搞到第i个字符还有j个空位的方案数，对于那个两个相同字母之间的限制可以直接组合数搞。但是N最大可能有1Y，原串最大2K+，所以只要把j换成用了j个位置，然后就可以直接DP了。（然而我还并没有写= =）

还有道题：要将1-n分成两个集合，使得不存在不同的三个数x、y、z同时存在一个集合里面使得xy=z。n<=10w

题解：考场上面就觉得很神，于是照着它给的50分线也就是n<=50交了张表，就没想太多了= =。后来题解里面说n>96时答案就是0了，于是应该交一张96的表就可以A了= =。出题人sxbk！

最近做了两套汪文潇和镇海的卷子，都考爆了，两天不仅成绩不好，而且还被自己wgy和Fadeness虐了（虽然两个都是因为数据水A的题），跟前几次集训状态相比感觉在考场上面能想出正解了（然并卵），然而还是会考挂，一是思路不清晰，很容易想错或者看错题，所以只写对了暴力完全就没有任何优势，二虽然这两场不明显，但是感觉还是代码能力弱了。除了能力问题就是整个人真的状态很萎，还是很容易弃疗，对自己还是太不自信了，有的时候真的觉得自己太弱了。还有就是最近实在是太摆了，说好的刷题量完全没上去。话说我这么萎我还能撑到什么时候？

题意：有两个长度为n的序列a、b，序列里面的每个数在1~n之间，求有多少个长度为n的排列c，使得a[c[i]]=c[b[i]]，并输出其中一个方案

题解：第一次感觉自己的思维还不是那么没救，虽然在考试最后30分钟想出来也没什么用= =。想了个把小时= =，首先看到问题感觉是置换群相关，或许会是polya计数法的奇怪运用？一直在画映射的图，感觉记不起来有什么相似的模型，想了很久差点就要弃(shui)疗(zhao)了，然后脑洞了一下试了下将这个画成第二题的环套树森林，就是对于每个i，i的父亲是a[i]，然后成了一个环套树，b也这么建，然后看图就可以很容易知道题目的要求变成了求a和b的映射使得两个森林同构。然后就可以有很多乱搞了。首先判断两个森林是不是同构的，这个总感觉最近碰到过一个相似的题目，但是那个是好像是用DP的= =，然而我感觉只会用hash的搞法。然后计算方案肯定是第i层的映射第i层的，尝试从第一层搞到最后一层，那么子树同构的结点肯定可以相互映射，那么如果a中有i个节点的子树同构，就可以把答案乘以i!，像这样子全部乘起来就是了= =那么环套树感觉又特殊一点，判断的时候用最小表示法，算的时候也是求出最小循环子串，貌似kmp相关？然后其他地方都差不多了吧，貌似求一组方案可以随便搞的样子。。。

题意：给定大小为20W的环套树森林，然后有20W组总共100W的染色，每组染色独立，染色是将一些点染成白点一些染成黑点，求每一组中“对于所有黑点是白点的祖先的二元组中黑点到白点路径上的边编号最大值”的最小值。

题解：题目是水题，但是艹蛋的题目大意（其实就是我语文不好啊！）坑了我两次，第一次naive我不记得是怎么理解的了，我竟然还写完了直到被样例卡住才反应过来，然后第二次我以为是求所有二元组中白点的父亲编号的最小值，然后一直在想线性做法= =（之前碰到过明明复杂度是n log n，而且n是100w的然后被卡掉了= =，这种情况后面也碰到过几次，完全搞怕了），最后还是写了线段树，如果理解对题意的话就应该还要加一个主席树查询最大值。如果根部有环的话就是缩点然后乱搞就是了（貌似这样还要加一棵主席树= =）总而言之如果没理解错题意感觉不难。