NationalDay1

今天ATP学姐来讲课啦。

在记录讲课内容及题解前先看道以前做过的DP

[HAOI2009]逆序对数列

题目描述

对于一个数列{ai},如果有iaj,那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列,可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个?

输入输出格式

输入格式:

第一行为两个整数n,k。

输出格式:

写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对10000求余数后的结果。

输入输出样例

输入样例#1:

1
4 1

输出样例#1:

1
3

说明

样例说明:

下列3个数列逆序对数都为1;分别是1 2 4 3 ;1 3 2 4 ;2 1 3 4;

测试数据范围

30%的数据 n<=12

100%的数据 n<=1000,k<=1000

题解

现在已经不难想到状态 , 设

表示前i个数产生j个逆序对数的方案数。

由于下一个数一定更大,所以转移就是:

这个式子还是有点问题的,因为当前加的这个数最多产生i对逆序对数,因此加的时候要减掉(j-i)的逆序对数的方案。

也就是这样

程序实现这个递推有点技巧,下面是Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// luogu-judger-enable-o2
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#define maxn 3005
#define mod 10000
long long n , k , f[maxn][maxn*2];
int main()
{
scanf("%lld%lld",&n,&k);
for(int i = 1 ;i <= n ; i++)
f[i][0] = 1;
for(int i = 2 ; i <= n ; i++)
{
long long sum = 0;
for(int j = 0 ; j <= k ; j++)
{
sum += f[i-1][j]%mod , sum %= mod;
f[i][j] = sum%mod;
if(j-i+1 >= 0)((sum-=f[i-1][j-i+1])+=mod)%mod;
}
}
printf("%lld\n", f[n][k]%mod);

}

接下来是几道矩阵快速幂的递推题

HDU 2604

•题目大意:给定一个数字L,求有多少个长度为L且仅有字母m和f的字符串满足串中不出现子串fmf和fff。答案对一个数字M取模

•多组数据,L不超过10^6

其实HDU原题是2^l….

突然发现HDU TM说的就是L…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
int l , mod;
struct Matrix{
int mat[10][10] , n , m;
Matrix(){
n = 9 , m = 9;
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= m ; ++j)
mat[i][j] = 0;
}
}F0 , F;
Matrix operator*(const Matrix& x , const Matrix& y)
{
Matrix ans;
if(x.m != y.n) return ans;
ans.n = x.n , ans.m = y.m;
for(int i = 1 ; i <= ans.n ; ++i)
for(int j = 1 ; j <= ans.m ; ++j)
for(int k = 1 ; k <= x.m ; ++k){
ans.mat[i][j] += x.mat[i][k] * y.mat[k][j] , ans.mat[i][j] %= mod;
ans.mat[i][j] %= mod;
}

return ans;
}
Matrix pow(const Matrix& x , ll y)
{
Matrix ans , base;
ans.n = ans.m = base.n = base.m = x.n;
for(int i = 1 ; i <= x.n ; ++i)
ans.mat[i][i] = 1;
base = x;
while(y)
{
if(y&1) ans = ans * base;
base = base * base;
y /= 2;
}
return ans;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
F0.n = 1 , F0.m = 4;
F0.mat[1][1] = 9 , F0.mat[1][2] = 6 , F0.mat[1][3] = 4 , F0.mat[1][4] = 1;
F.n = F.m = 4;
F.mat[1][1] = F.mat[3][1] = F.mat[4][1] = F.mat[1][2] = F.mat[2][3] = F.mat[3][4] = 1;
while(scanf("%d%d",&l,&mod) != EOF)
{

if(l == 0) {printf("0\n") ; continue;}
if(l <= 4)
{
printf("%d\n",F0.mat[1][4-l+1]%mod);
continue;
}
Matrix ans = F0 * pow(F,l-4);
printf("%d\n",ans.mat[1][1]%mod);
}

}

近期换了华为手机,系统是EMUI 8.2.0,在安装google服务的时候颇费了一番周折。

之前能用的一些google服务安装器在该系统上均无法工作,最后从应用汇上下载了一个gms安装软件,可是华为系统提示“该应用会破坏系统,禁止安装”。
开启设置里面的未知来源应用下载,并禁用外部来源应用检查,还是不允许安装。

后来从花粉俱乐部了解到可以通过以下方式安装:

  1. 把该apk拷贝到电脑上
  2. 进入设置→开发人员选项,关闭监控ADB安装应用
  3. 通过adb安装应用。(也可以在USB连接的情况下通过360手机助手、豌豆荚等软件安装该应用)

安装完成后手机会重启,然后根据提示开启google服务的各项权限,后面再配合vpn(本人使用的是影梭,Shadowsocks),就可以方便使用google系列应用。

可以从下面的链接下载gms安装器: http://data.coderhuo.tech/blog/google_service_tool/gms.apk