NationalDay1

Veröffentlicht am | Edited on

今天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);
    }

}