bef->NO.13

Veröffentlicht am | Edited on

[NOI2012]随机数生成器

题目描述

栋栋最近迷上了随机算法，而随机数是生成随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数m,a,c,X[0],按照下面的公式生成出一系列随机数{Xn}：

1
X[n+1]=(aX[n]+c) mod m

其中mod m表示前面的数除以m的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。

用这种方法生成的序列具有随机序列的性质，因此这种方法被广泛地使用，包括常用的C++和Pascal的产生随机数的库函数使用的也是这种方法。

栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道X[n]是多少。由于栋栋需要的随机数是0,1,…,g-1之间的，他需要将X[n]除以g取余得到他想要的数，即X[n] mod g，你只需要告诉栋栋他想要的数X[n] mod g是多少就可以了。

输入输出格式

输入格式：

输入包含6个用空格分割的整数m,a,c,X[0],n和g，其中a,c,X[0]是非负整数，m,n,g是正整数。

输出格式：

输出一个数，即X[n] mod g

输入输出样例

输入样例#1：

1
11 8 7 1 5 3

输出样例#1：

1
2

说明

计算得X[n]=X[5]=8,故

100%的数据中

题解

非常简单的矩阵递推，不过要注意坑人的慢速乘。

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
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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
ll n , x0 , m , a , c , g;
struct Matrix{
    ll mat[4][4] , n , m;
    Matrix(){
        n = m = 3;
        for(int i = 0 ; i <= n ; ++i)
            for(int j = 0 ; j <= m ; ++j)
                mat[i][j] = 0;
    }
    inline void unit(){
        for(int i = 1 ; i <= n ; ++i)
            mat[i][i] = 1;
    }
}F0,F;
inline ll mul(ll x , ll y) {//龟速乘法
    ll ret = 0;
  for(ret = 0; y; y >>= 1) {
    if (y & 1) ret = (ret + x) % m;
    x = (x + x) % m;
  }
  return ret;
}
inline 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] += mul(x.mat[i][k] , y.mat[k][j]) ) %= m;
    return ans;
}
inline Matrix pow(const Matrix& x , ll y)
{
    Matrix ans , base;
    ans.unit() , base = x;
    while(y)
    {
        if(y&1) ans = ans * base;
        base = base * base ;
        y /= 2;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
    F0.n = 1 , F0.m = 3;
    F0.mat[1][1] = x0 , F0.mat[1][2] = 0 , F0.mat[1][3] = c;
    F.mat[1][1] = a , F.mat[3][1] = 1 , F.mat[1][2] = 1 , F.mat[3][3] = 1;
    Matrix ans = F0 * pow(F,n);
    printf("%lld\n",ans.mat[1][1] % g);
}

三素数数

题目背景

蛟川书院的一道练习题QAQ

题目描述

如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。

输入输出格式

输入格式：

一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。

输出格式：

一个整数，表示n位三素数的个数m，要求输出m除以10^9 + 9的余数。

输入输出样例

输入样例#1：

1
4

输出样例#1：

1
204

说明

区域动归QAQ

题解

蛟川书院的dp好题

显然要求任意连续3位是质数 ， 我们只需要保留最后两位然后做数位dp就好了

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
27
28
29
30
31
32
33
34
35
36
37
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 10005
#define mod 1000000009
int f[maxn][100] , prime[1005] , cnt , tr[305] , n , trn;
long long ans;
bool inprime[1005];
inline void Sieve(int n)
{
    for(int i = 2 ; i <= n ; ++i)
    {
        if(!inprime[i]) prime[++cnt] = i;
        for(int j = 1 ; j <= cnt && i * prime[j] <= n ; ++j)
            inprime[i*prime[j]] = true;
    }
    int k = 0;
    while(prime[++k] <= 100);
    trn = cnt - k + 1;
    for(int i = k ; i <= cnt ; ++i)
        tr[i-k+1] = prime[i];
}
int main()
{
    scanf("%d",&n);
    Sieve(1000);
    for(int i = 1 ; i <= trn ; ++i)
        f[3][tr[i]%100] += 1;
    for(int i = 4 ; i <= n ; ++i)
        for(int j = 1 ; j <= trn ; ++j)
            (f[i][tr[j]%100] += f[i-1][tr[j]/10]) %= mod;
        for(int j = 1 ; j <= 99; ++j)
            (ans += f[n][j]) %= mod;
    printf("%lld",ans);
}

注意，最后的统计答案不能和初始化一样！

[ZJOI2010]数字计数

题目描述

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

输入输出格式

输入格式：

输入文件中仅包含一行两个整数a、b，含义如上所述。

输出格式：

输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

输入输出样例

输入样例#1：

1
1 99

输出样例#1：

1
9 20 20 20 20 20 20 20 20 20

说明

30%的数据中，

100%的数据中，

题解

显然是跑数位DP

然后我就写挂了。

然后换了优雅的记忆化搜索就AC了（记忆化搜索真好可是我不擅长QAQ）

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
// using namespace std;
typedef long long ll;

const int N = 15;
ll f[N][2][N][2];
int num[N];

ll dfs(int len, bool issmall, int sum, bool zero, int d)
{
    ll ret = 0;
    if (len == 0) return sum;
    if (f[len][issmall][sum][zero] != -1) return f[len][issmall][sum][zero];
    for (int i = 0; i < 10; i ++){
        if (!issmall && i > num[len]) break;
        ret += dfs(len-1, issmall || (i<num[len]), sum+((!zero || i) && (i==d)), zero && (i == 0), d);

    }
    f[len][issmall][sum][zero] = ret;
    return ret;
}

ll solve(ll x, int d)
{
    int len = 0;
    while (x){
        num[++ len] = x%10;
        x /= 10;
    } //数字转数位
    std::memset(f, -1, sizeof f); //初始化
    return dfs(len, 0, 0, 1, d); //开始在第len位上，最高位只能枚举到num[len]所以issmall是0，sum=0，有前导0。
}

int main()
{
    ll a, b; //注意都要开long long
    scanf("%lld%lld", &a, &b);
    for (int i = 0; i < 10; i ++)
        printf("%lld%c", solve(b, i)-solve(a-1, i), i == 9 ? '\n' : ' ');
    return 0;
}

[ZJOI2008]骑士

题目描述

Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。

最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。

骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。

战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。

为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

输入输出格式

输入格式：

输入文件knight.in第一行包含一个正整数N，描述骑士团的人数。

接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

输出格式：

输出文件knight.out应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

输入输出样例

输入样例#1：

1
2
3
4
3
10 2
20 3
30 1

输出样例#1：

1
30

说明

对于30%的测试数据，满足N ≤ 10；

对于60%的测试数据，满足N ≤ 100；

对于80%的测试数据，满足N ≤ 10 000。

对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。

题解

一句话就是基环树森林最大点独立集的和。

轻松想出来然后一直挂。。。

就是对每个联通块找出环上两点然后两遍树形dp，然后取两个根分别不选的最大值 ， 原因很好想，假如当前根选了，断边所连得点就有后效性了。

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
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
67
68
69
70
// luogu-judger-enable-o2
#include <cstdio>
#include <iostream>
#include <cstring>
#define N 1000010
using namespace std;
int fun[N],a,b;
long long f[N][2];
struct node
{
    int next,to,v;
}e[2000010];
int st[1000010],vis[N],n,s,tot,x1,x2,E;
void add(int x,int y)
{
    e[tot].to=y,e[tot].next=st[x],st[x]=tot++;
    //e[++tot].to=x,e[tot].v=z,e[tot].next=st[y],st[y]=tot;
}
void find_circle(int x,int pre)
{
    vis[x]=1;
    for (int i=st[x];~i;i=e[i].next)
    {
        if ((i^1)==pre) continue;
        if (vis[e[i].to])
        {
            x1=x,x2=e[i].to;
            E=i;
            continue;
        }
        find_circle(e[i].to,i);
    }
}
void dfs(int x,int pre)
{
    f[x][0]=0;
    f[x][1]=fun[x];
    for (int i=st[x];~i;i=e[i].next)
    {
        if ((i^1)==pre) continue;
        if (i==E || (i^1)==E)
            continue;
        dfs(e[i].to,i);
        f[x][1]+=f[e[i].to][0];
        f[x][0]+=max(f[e[i].to][1],f[e[i].to][0]);
    }
    // printf("%lld %lld\n",f[x][0] , f[x][1]);
}
main()
{
    memset(st,-1,sizeof st);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&fun[i],&b),add(i,b),add(b,i);
    long long ans=0;
    for (int i=1;i<=n;i++)
    {
        if (vis[i]) continue;
        find_circle(i,-2);
        // printf("%d %d\n",x1,x2);
        dfs(x1,-1);
        long long temp=f[x1][0];
        // printf("%lld ",temp);
        dfs(x2,-1);
        temp=max(temp,f[x2][0]);
        // printf("%lld",f[x2][0]);
        ans+=temp;
    }
    printf("%lld",ans);
}

[SDOI2009]HH去散步

题目描述

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径

输入输出格式

输入格式：

第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的 路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。

接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai != Bi，但 不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N − 1。 同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 答案模45989。

输出格式：

一行，表示答案。

输入输出样例

输入样例#1：

1
2
3
4
5
6
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2

输出样例#1：

1
4

说明

对于30%的数据，

对于100%的数据，

题解

这道题好啊，是一道矩阵优化图上dp的题，也是我做过第一个类型的。

首先分析题目，要求不能走回边，但是可以走环，意味着dp状态只需要知道上一条边走的是什么就可以了，不能用点来做状态。

然后dp过程也比较好想

其实就是让你求有多少条长度为t的路径，但是有一个特殊条件：不能走过一条边以后又立刻反着走一次（如果两次经过同意条边中间隔了别的边是可以的）

如果没有这个特殊条件，我们很容易想到dp做法：设

表示第i个时刻（初始算0），走到第j个点的答案总数

但是这里要限制不能反复走，那么直接设点会导致信息丢失

那我们怎么样才能让保存当前所在点的情况下，不丢失最后一条边的信息呢？

答案非常显然，我们只要设

表示第i个时刻（初始算0），走到第j条边的终点（也就是刚刚经过了第j条边到达这里）的答案总数，就可以了

此时我们因为知道第j条边的所有信息，而第j条边的信息中又包括了当前所在节点，所以我们继续转移需要的信息都收集全了

转移就是从当前点u开始，枚举从u出发的边k，向

转移即可

然而这里有个问题：T太大了，直接转移肯定爆炸，那怎么办呢？

我们观察可得，对于每个

，只要jj确定了，那么他应该往哪些状态转移也就确定了，同时这个转移一定是线性的（也就是dpdp这一项一定是一次的）

那我们还等什么呢？矩阵快速幂上啊！

我们构造转移矩阵B和初始状态矩阵A，但是这里又有一个问题：初始只有一个出发节点，并没有不能走哪条边的限制，但是转移矩阵B又依赖于这个限制，怎么办呢？

这好说，我们只要把A矩阵从所有

变成所有

就好了

这时答案矩阵

只要取出答案矩阵中所有终点是给定终点的边的答案之和，输出即可

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
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 180
#define maxm 300
#define ll long long
#define mod 45989
ll n , m , s , t , p , cnt = 1, head[maxn];
struct Matrix{
    ll mat[maxm][maxm] , n , m;
    Matrix(){
        n = m = maxm - 1;
        for(int i = 0 ; i <= n ; ++i)
            for(int j = 0 ; j <= m ; ++j)
                mat[i][j] = 0;
    }
    inline void Unit()
    {
        for(int i = 1 ; i <= n ; ++i)
            mat[i][i] = 1;
    }
}A , B;
struct edge{
    ll next , to;
}e[maxn * 3];
inline void add(ll x , ll y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
inline Matrix operator*(const Matrix& x , const Matrix& y)
{
    Matrix 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]) %= mod;
    return ans;
}
ll Rev(ll x)
{
    return (x ^ 1);
}
Matrix pow(const Matrix& x , ll y)
{
    Matrix ans , base;
    ans.Unit() , base = x;
    while(y)
    {
        if(y&1) ans = ans * base;
        base = base * base;
        y /= 2;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld",&n,&m,&p,&s,&t) , ++s , ++t;
    ll x , y ;
    for(int i = 1 ; i <= m ; ++i)
        scanf("%lld%lld",&x,&y) , add(x+1,y+1) , add(y+1,x+1);
    A.n = 1 , A.m = B.m = B.n = cnt;
    for(int i = 1 ; i <= cnt ; ++i)// the transfer Matrix
    {
        ll u = e[i].to ;
        for(int j = head[u] ; j ; j = e[j].next)
            if(j != Rev(i))
                ++ B.mat[i][j] ;
    }
    for(int i = head[s] ; i ; i = e[i].next)
        ++ A.mat[1][i];
    Matrix ans = A * pow(B , p - 1);
    ll tot = 0;
    for(int i = head[t] ; i ; i = e[i].next)
        (tot += ans.mat[1][Rev(i)]) %= mod;
    printf("%lld",tot);
}

[POI2012]OKR-A Horrible Poem

题目描述

给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。

如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

说明

给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。

如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

n <= 500000 , q <= 2000000

题解

第一反应是前缀Hash，显然的确要用到。

然后一个显而易见的事实是假如k是循环节，n*k也是循环节，这一点很重要，我们只需要枚举区间长度质因子即可。

n是[l,r]这一段的循环节 的充要条件是 [l,r-n]和[l+n,r]相同（利用这个性质我们在判断是否为循环节是可以做到O1hash

然后就是代码实现了，注意1~n内的数

的质因数分解方法，由next数组实现。

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
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 750010
#define seed 357
#define ull unsigned long long
char s[maxn] ;
ull h[maxn] , g[maxn];
int n , q;
struct Node{
    int l , r;
}p[maxn];
int prime[maxn] , cnt , next[maxn] , fac[maxn/20] , fan;
bool inprime[maxn];
inline ull pow(ull x , ull y)
{
    ull ans = 1 , base = x;
    while(y)
    {
        if(y&1) ans *= base;
        base *= base;
        y /= 2;
    }
    return ans;
}
inline void euler(int n)
{
    for(int i = 2 ; i <= n ; ++i)
    {
        if(!inprime[i]) prime[++cnt] = i , next[i] = i;
        for(int j = 1 ; j <= cnt && i * prime[j] <= n ; ++j)
        {
            inprime[i*prime[j]] = true;
            next[i*prime[j]] = prime[j]; //efficient factor the number
            if(!(i%prime[j]))   break;
        }
    }
}
inline void GetHash()
{
    for(int i = 1 ; i <= n ; ++i)
        h[i] = h[i-1] * seed + s[i];
    g[0] = 1;
    for(int i = 1 ; i <= n ; ++i)
        g[i] = g[i-1] * seed;
}
inline ull qHash(int l , int r)
{
    int len = r - l + 1;
    ull ans = h[r] - h[l-1] * g[r-l+1];
    return ans;
}
inline void solve()
{
    for(int i = 1 ; i <= q ; ++i)
    {
        std::memset(fac,0,sizeof(fac)) , fan = 0;
        int len = p[i].r - p[i].l + 1 , l = p[i].l , r = p[i].r;
        // printf("%d\n",len);
        while(len != 1)
        {
            fac[++fan] = next[len];
            len /= next[len] ;
        }
        // for(int j = 1 ; j <= fan ; ++j)
        //     printf("%d ",fac[i]);
        // putchar(10);
        len = r - l + 1;
        for(int j = 1 ; j <= fan ; ++j)
        {
            int t = len / fac[j];
            if(qHash(l,r-t) == qHash(l+t,r)) len = t;
        }
        printf("%d\n",len);
    }
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    euler(600000);
    scanf("%d",&q);
    for(int i = 1 ; i <= q ; ++i)
        scanf("%d%d",&p[i].l,&p[i].r);
    GetHash();
    // printf("%llu %llu" , qHash(1,3) , qHash(4,6));
    solve();
}