【20180110】省选模拟赛

0+0+70=70
期望：70+100+70=240
我还是个傻子

t1 有毒的土豆排序

Description

SiriusRen有 n 个土豆，土豆排成一排，从左到右依次编号为1~n。每个土豆都有自己的毒性，SiriusRen想让土豆们按照毒性从小到大排序。
现在有m次操作，每次选一个土豆。当土豆被选中的时候，这个土豆会向后面的土豆（编号大于该土豆的土豆）发出指令。但是由于毒性，只有毒性低于该土豆的土豆才会听指令。
这些土豆会按照毒性从小到大顺序重新排列在这些土豆之前的位置上，并重新编号。
SiriusRen想知道，每次操作之后，土豆毒性的逆序对有多少个。

Input

第一行包含两个整数 n，m，表示土豆的数量和SiriusRen操作的次数。
第二行有n个数字，A1,A2……An（Ai<1e9），分别表示编号为 1，2……n 的土豆的毒性。
接下来m行，每行一个整数k，代表SiriusRen选的土豆是第k个。

Output

m+1行，每行一个整数，分别代表一开始的逆序对数与进行了i次操作后的逆序对数。

Sample Input 1 

3 2
2 3 1
1
1

Sample Output 1

2
1
1

Hint

样例解释：
初始逆序对数量为2。
选中第一个数的时候，重排&重编号之后序列变成了1 3 2，逆序对数变成了1。
再次选中第一个数，后面没有毒性小于1的数，所以都不会动。

数据范围：

对于 40%的数据，1 <= n <= 20，1 <= m <= 20。
对于 70%的数据，1 <= n，m <= 10^3。
对于 100%的数据，1 <= n，m <= 10^5。

良心提醒：土豆的毒性可能相同。

Source

By SiriusRen

题解&反思

t2 窝瓜走路

Description

3*3的方格里有九个窝瓜分别在不同的格子里。窝瓜可以选择不动或者往上下左右相邻的格子移动（一个格子里可以放得下很多窝瓜）。
求：经过n步有多少种不同的走法，使得最终的每个格子里都有一个窝瓜。答案\( mod10^9+7 \)

Input

一行一个整数n

Output

方案数\( mod10^9+7 \)

Sample Input 1


1

Sample Output 1

229

Hint

对于40%的数据，1<=n<=10
对于70%的数据，1<=n<=10^6
对于100%的数据，1<=n<=10^18

Source

By SiriusRen

题解&反思

因为在矩阵乘法里把0矩阵写成了单位矩阵，导致丢了100分。
做法很简单，a[i][j]表示j步挪成当前在i格子的方案数，初始化就是能互相转移的格子(i,j),a[i][j]=1，然后矩乘n次即可。记得分清单位矩阵和0矩阵

t3不知道起什么名字好的数学题

Description

愚蠢的yzy看不懂题面。
题意简化成：
求gcd(i,j)的k次方之和(1<=i,j<=n)

Input

一行两个整数n,k。

Output

一行表示答案mod10^9+7

Sample Input 1


2 2

Sample Output 1

7

Hint

1<=i,j<=n

数据范围：

对于 40%的数据，1<=n<=10^3；
对于 70%的数据，1<=n<=10^6；
对于 100%的数据，1<=n<=10^10，1<=k<=5

Source

By SiriusRen

题解&反思

我以为我能写正解，结果花了3h发现有个算法不会，导致t1t2爆炸。
推是很好推，记得前缀和取模
\(\(
ans=\sum_{d=1}^{n}(d^k\sum_{i=1}^{n}\sum_{j=1}^{n}\left e[ gcd(i,j)==d \right ])
\)\)
\[ans=\sum_{d=1}^{n}(d^k\sum_{i=1}^{n}\sum_{j=1}^{\frac{n}{d} }\left e[ gcd(i,j)==d \right ])\]
然后要学一下杜教筛吧……