直接暴力读入所有字符串，判断最后两位是否为 'A' 和 'K' 即可。

B：114514

114514=2*31*1847
所以我们选出来的子集去重后只有O( 1 )种可能性
我们可以选的子集有
114514
2*57257
31*36943
62*18476
2*31*1847
1*114514
1*2*57257
1*31*3694
1*62*1847
1*2*31*1847
所以我们暴力枚举所有可能的情况就可以了
时间复杂度O(n)

我们发现要求的数列实际上是 数列的自卷积。
通过随便简单推导可得：
然后可以直接暴力算出前几项，对于n ≤ 3的情况特判掉， n > 3时， 这个公式为线性齐次递推式，可以用矩阵加速运算求解。 时间复杂度：O( logn )

我们发现 满足排列。
首先考虑一对牌 能够产生的贡献，可以分为以下三种情况：
1. i在p[j] ， j在p[i]
2.上面条件只满足一个

3.上面条件都不满足
那么这样的话考虑怎么算这三种放法的方案数：
我们记录f[x][y]表示当前总共有(x+y)张牌，其中x张牌满足其对应的p[i]上已经有牌，y张牌满足其对应的p[i]上还没有牌。
1.第一种放法不会对别的牌产生任何干扰，即f[n-2][0]。
2.第二种放法只会影响一张牌，所以除了这两张牌以外还有一张牌的位置被占了，同时放的牌使得多出来一张牌它的p[i]没有被占，所以是f[n-3][1]
3.第三种放法影响了两张牌，所以出现了两张额外的牌他们的p[i]已经有牌，那么就是f[n-4][2]
上面的三种转移都是x+y+2=n
那么考虑预处理 ，可以进行如下递推：

首先如果都没有牌那么肯定只有一种方案。
如果没有牌的p[i]位置上被放了牌，那么多放一张牌相当于一个全排列，因此是阶乘的形式。
如果x和y都不等于0，考虑两种情况：
第一种它没有放在任何一张先前的牌的p[i]上，并且它的p[i]没有被先前的牌占据，那么相当于少了两个x，多了一 个y，这样的话除了加入的这个x总共有(x-1)种可选择位置，因此系数是(x-1)
第二种情况它放在了一个先前空的p[i]上，那么跟之前类似。
然后我们再考虑知道这个方案数之后该怎么算贡献。
如果i在p[j]且j在p[i]，那么必然系数就是max(0,p[j]-p[i])（因为只有权值大才会算贡献，因此用0除掉负数的情况）
如果上述两个条件只满足一个，

考虑一个简单的容斥，两个符合条件的区间是总区间挖去[pi,pj]，最后发现a1的情况被我们算了两次，所以去掉即 可。
如果上述两个条件都不太符合，那么

是一个类似上面的容斥，不赘述了。
然后最后累计进答案的时候由于要乘上权值差，多乘一个(j-i)在最前面就可以了。
注意后两者要讨论n是否>=3和>=4.

E：树上逆序对

考虑一前一后的两个数什么时候形成逆序对。

很显然绝对值大的符号决定了是否形成逆序对。

那么只需分别统计一 个节点它的祖先和子树有多少比它小的节点。

有两个方法（本题都行）：

1.直接树剖

2.dfs序+树状数组做子树， vector做祖先。 然后做个背包就OK了，注意此处需要使用bitset加速。

先研究全局查询的情况，考虑离散化后所有值域区间对应的不同的序列只有O( n^2 )种，我们可以分治来维护两边的最大前缀和，最大后缀和，最大子段和，合并的时候，左儿子有个答案矩阵，右儿子也有个同规模的答案矩阵，我们把这两个稀疏化一下（大概就是说你每次把块内存在的值归并上来，这个矩阵会变大常数倍），然后就可以合并了，每次合并的是O( n^2 )的
所以这里我们有T(n)=2T(n/2)+O(n^2)，解得T(n)=O(n^2)
所以我们先在外层对序列分块，这样有O( sqrtn )个O( sqrtn )大小的块，每个块的分治预处理代价是T( sqrtn ) = O( n )的，所以预处理的总复杂度是O( sqrtn ) * O( n ) = O( nsqrtn )的
我们对序列每个块逐个处理，然后每次合并出答案即可
时间复杂度O( (n + m)sqrtn )，空间复杂度O( n + m )