bef-> NO.12

Veröffentlicht am

NOIp 2017 D1T3 逛公园

题目描述

策策同学特别喜欢逛公园。公园可以看成一张NN个点MM条边构成的有向图，且没有 自环和重边。其中1号点是公园的入口，NN号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从1号点进去，从NN号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到NN号点的最短路长为dd，那么策策只会喜欢长度不超过d + Kd+K的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对PP取模。

如果有无穷多条合法的路线，请输出-1−1。

输入输出格式

输入格式：

第一行包含一个整数 TT, 代表数据组数。

接下来TT组数据，对于每组数据： 第一行包含四个整数 N,M,K,PN,M,K,P，每两个整数之间用一个空格隔开。

接下来MM行，每行三个整数a_i,b_i,c_iai,bi,ci，代表编号为a_i,b_iai,bi的点之间有一条权值为 c_ici的有向边，每两个整数之间用一个空格隔开。

输出格式：

输出文件包含 TT 行，每行一个整数代表答案。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0

输出样例#1：

1
2
3
-1

说明

【样例解释1】

对于第一组数据，最短路为 33。 $1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5$ 为 33 条合法路径。

【测试数据与约定】

对于不同的测试点，我们约定各种参数的规模不会超过如下

测试点编号 TT NN MM KK 是否有0边
1 5 5 10 0 否
2 5 1000 2000 0 否
3 5 1000 2000 50 否
4 5 1000 2000 50 否
5 5 1000 2000 50 否
6 5 1000 2000 50 是
7 5 100000 200000 0 否
8 3 100000 200000 50 否
9 3 100000 200000 50 是
10 3 100000 200000 50 是

对于 100%的数据,

数据保证：至少存在一条合法的路线。

题解

表示除了30分最短路计数以外并不会这道题，这道题好难啊qwq

这道题可以dp，似乎很容易想到的一种做法是先从n跑一边单源最短路，然后设

表示点i比i的最短路长j的方案数，然后按照到点1的最短路长度为第一关键字 ， 拓扑序为第二关键字转移。

然后这个可以记忆化搜索。

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
91
92
93
94
95
96
97
98
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define mp(x,y) std::make_pair((x),(y))
#define pii std::pair<int,int>
#define maxn 100005
#define maxk 52
int head[maxn] , d[maxn] , f[maxn][maxk] , cnt , n , m , T , k , p , cntr , h[maxn] , flag , ans;
bool vis[maxn] , get[maxn][maxk];
struct edge{
    int next , to , dis;
}e[maxn*4] , r[maxn*4];
inline void add(int x , int y , int dis)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    e[cnt].dis = dis;
    head[x] = cnt;
}
inline void addr(int x , int y , int dis)
{
    r[++cntr].next = h[x];
    r[cntr].to = y;
    r[cntr].dis = dis;
    h[x] = cntr;
}
inline void init()
{
    std::memset(head,0,sizeof(head));
    std::memset(e,0,sizeof(e));
    std::memset(r,0,sizeof(r));
    std::memset(d,0,sizeof(d));
    std::memset(f,-1,sizeof(f));
    std::memset(h,0,sizeof(h));
    cnt = 0 , cntr = 0 , flag = 0 , ans = 0;
    scanf("%d%d%d%d",&n,&m,&k,&p);
    int x , y , dis;
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d%d",&x,&y,&dis) , add(x,y,dis) , addr(y,x,dis);
    // puts("OK");
}
inline void SPDIJ(int s)
{
    std::priority_queue<pii , std::vector<pii> , std::greater<pii> > q;
    std::memset(d,0x3f,sizeof(d));
    std::memset(vis,false,sizeof(vis));
    d[s] = 0;
    q.push(mp(d[s],s));
    while(!q.empty())
    {
        int k = q.top().second;
        q.pop();
        if(vis[k])  continue;
        vis[k] = true;
        for(int i = h[k] ; i ; i = r[i].next)
            if(d[k] + r[i].dis < d[r[i].to])
                d[r[i].to] = d[k] + r[i].dis , q.push(mp(d[r[i].to] , r[i].to));//new style , warning!
    }
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("%d ",d[i]);
    // puts("SPDIJ");
}
int dfs(int x , int v)
{
    if(get[x][v]){flag = 1 ; return 0;}
    if(f[x][v] != -1) return f[x][v];
    int ans = 0;
    get[x][v] = true;
    for(int i = head[x] ; i ; i = e[i].next)
    {
        int nowv = v - (d[e[i].to] + e[i].dis - d[x]);
        if(nowv > k || nowv < 0) continue;
        ans = (ans + dfs(e[i].to , nowv)) % p;
        if(flag) return 0;
    }
    get[x][v] = false;
    if(x == n && v == 0) ++ans;
    return f[x][v] = ans;
}
int main()
{
    // freopen("garden.in","r",stdin);
    scanf("%d",&T);
    while(T--){
        init();
        SPDIJ(n);
        // putchar(10);
        for(int i = 0 ; i <= k ; ++i)
            ans += dfs(1,i), ans %= p , std::memset(get,false,sizeof(get));;
        // for(int i = 0 ; i <= k ; ++i)
        //     printf("%d\n",f[1][i]);
        if(flag) puts("-1");//the 0 rings
        else printf("%d\n",ans);
    }
}

[AHOI2009]中国象棋

题目描述

这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

输入输出格式

输入格式：

一行包含两个整数N，M，之间由一个空格隔开。

输出格式：

总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。

输入输出样例

输入样例#1：

1
1 3

输出样例#1：

1
7

说明

样例说明

除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有222-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

题解

首先对于50分，我们可以对每行压缩状态，然后暴力跑状态压缩就可以了。

但是题目显然要求一个

级别的算法，这时候我们发现，状态压缩之所以效率低是因为没有很好地利用组合数学来快速对一样的情况计数

我们发现，我们每行最多填两个，也就是

个状态这比

要小得多。其次我们并不需要知道当前到底是那些列有一个，哪些列有两个。

因此我们可以用组合来优化。

设

表示前i行填完有j列1和k列2的方案数。

然后分情况来转移

确定情况

  1. 我们可以在当前第i行不放棋子.
  2. 我们可以在当前第i行放一个棋子
  3. 我们可以在当前第i行放两个棋子.

接下来就需要分类讨论这些情况.

分类讨论

一.不放棋子

我们可以直接继承上面的状态.即

二.放一个棋子

显然我们不会选择放在有两个棋子的列.

因此存在情况如下

img

解释：
放在一个棋子的列

我们在某一个有一个棋子列放置棋子,会使这一列变为有两个棋子.

即我们要得到

需要在j+1个有一个棋子的列放置棋子,变为j个有一个棋子的列

而我们又会得到一个新的有两个棋子的列.因此我们之前必须有k-1个有两个棋子的列.

即

的状态可以传递给

而我们又可以在(j+1)中的任何一列放置这一个棋子.

因此我们要

放在没有棋子的列

在一个没有棋子的列放置棋子,我们会得到一个新的有一个棋子的列.

即我们要从j-1得到j.

而这个时候,我们有两个棋子的列的数量不会变,所以从k传递即可.

即

的状态可以传递给

又因为我在空列中的任何一列放置这个棋子.

所以要

三.放两个棋子

这个时候情况会多一个.先请大家自己考虑一下.

这个时候存在情况如下

img

解释
一个放在有一个棋子的列,一个放在没有棋子的列

这个时候,我们放置之后 :

一个没有棋子的列会变成一个有一个棋子的列,而一个有一个棋子的列会变成一个有两个棋子的列。

此时我们发现,

有一个棋子的列的数量不会变,因此第二维依旧为j，

又因为我们会新增一个有两个棋子的列,所以我们需要从k-1转移过来.

又因为我们可以在有一个棋子的列随便放,空列随便放.

根据乘法原理,需要

都放在没有棋子的列

此时我们放置之后

会增加两个新的有一个棋子的列.

因此我们需要从j-2转移过来.

而两个棋子的列的数量并不会改变,所以依旧为k

又因为在空列中我们随便放.

根据组合数学,需要

都放在有一个棋子的列

我们放置在有一个棋子的列之后：

这两个有一个棋子的列都会变成有两个子的列.

即j+2变成j，从k-2变成k

又因为这些有一个棋子的列我们随便选择.

根据组合数学,需要

注意细节，以及取模。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
#define mod 9999973
#define maxn 105
ll f[maxn][maxn][maxn] , n , m;
ll C(ll n)
{
    return n * (n-1) / 2;
}
int main()
{
    scanf("%d%d",&n,&m);
    f[1][0][0] = 1 ;
    f[1][1][0] = m ;
    f[1][2][0] = C(m);
    for(int i = 2 ; i <= n ; ++i)
        for(int j = 0 ; j <= m  ; ++j)
            for(int k = 0 ; k + j <= m ; ++k)
            {
                f[i][j][k] += f[i-1][j][k] , f[i][j][k] %= mod;//no one on this line
                //puts one
                if(j > 0)   f[i][j][k] += f[i-1][j-1][k] * (m - (j-1) - k) % mod , f[i][j][k] %= mod; // on the empty row
                if(j < m && k > 0)    f[i][j][k] += f[i-1][j+1][k-1] * (j + 1) % mod , f[i][j][k] %= mod;
                //puts two
                if(j > 1)    f[i][j][k] += f[i-1][j-2][k] * C(m - (j-2) - k) % mod , f[i][j][k] %= mod;//two empty rows
                if(k > 0)  f[i][j][k] += f[i-1][j][k-1] * j * (m - (k-1) - j) % mod , f[i][j][k] %= mod;//one&empty
                f[i][j][k] += f[i-1][j+2][k-2] * C(j+2) % mod , f[i][j][k] %= mod;

            }
    ll ans = 0;
    for(int i = 0 ; i <= m ; ++i)
        for(int j = 0 ; j + i <= m ; ++j)
            ans += f[n][i][j] , ans %= mod;
    printf("%lld",ans);
}

[CQOI2016]手机号码

题目描述

人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。

工具需要检测的号码特征有两个：号码中要出现至少 33 个相邻的相同数字；号码中不能同时出现 88 和 44。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。

手机号码一定是 11 位数，前不含前导的 00。工具接收两个数 LL 和 RR，自动统计出 [L,R][L,R] 区间内所有满足条件的号码数量。LL 和 RR 也是 1111 位的手机号码。

输入输出格式

输入格式：

输入文件内容只有一行，为空格分隔的 22 个正整数 L,RL,R。

输出格式：

输出文件内容只有一行，为 11 个整数，表示满足条件的手机号数量。

输入输出样例

输入样例#1：

1
12121284000 12121285550

输出样例#1：

1
5

说明

样例解释：满足条件的号码： 12121285000、 12121285111、 12121285222、 12121285333、 12121285550。

数据范围：

题解

简单的数位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
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
ll f[15][2][2][2][2][2][4][10] , L[20] , R[20] , ans;
inline void read(ll* s);
inline void DP();
int main()
{
    read(L) , read(R);
    DP();
    printf("%lld",ans);
}//如果连续的超过三个就更新noc，同时把它们都压到3上
inline void read(ll* s)
{
    int cnt = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0') ch = getchar();
    while(ch <= '9' && ch >= '0') s[++cnt] = ch - '0' , ch = getchar();
}
inline void DP()
{
    //init
    for(int i = L[1] ; i <= R[1] ; ++i){
        int _4 , _8 , _up , _dw;//exist 4 ? 8 ? on maxborder ? lowboler?
        _4 = (i==4 )? 1 : 0 , _8 = (i == 8) ? 1 : 0;
        _up = (i == R[1]) ? 1 : 0  , _dw = (i == L[1]) ? 1 : 0;
        f[1][_4][_8][0][_up][_dw][1][i] = 1;
    }
    for(int i = 1 ; i < 11 ; ++i)
        for(int _4 = 0 ; _4 <= 1 ; ++_4)
            for(int _8 = 0 ; _8 <= 1 ; ++_8)
                for(int con = 0 ; con <= 1 ; ++con)
                    for(int up = 0 ; up <= 1 ; ++up)
                        for(int dw = 0 ; dw <= 1 ; ++dw)
                            for(int nowc = 0 ; nowc <= 3 ; ++nowc)//tail continous
                                for(int la = 0 ; la <= 9 ; ++la)
                                    if(f[i][_4][_8][con][up][dw][nowc][la]){
                                        int n4 , n8 , is_con , nup , ndw , ncon;
                                            for(int now = 0 ; now <= 9 ; ++now){
                                                n4 = n8 = is_con = nup = ndw = ncon = 0;
                                                if(_4 || now == 4) n4 = 1;
                                                if(_8 || now == 8) n8 = 1;
                                                if(con) is_con = 1;
                                                if(n4 && n8) continue;
                                                if(up && now > R[i + 1]) continue;
                                                if(dw && now < L[i + 1]) continue;
                                                if(up && now == R[i + 1]) nup = 1;
                                                if(dw && now == L[i + 1]) ndw = 1;
                                                if(now == la) ncon = nowc + 1;
                                                else ncon = 1;
                                                if(ncon >= 3) is_con = 1 , ncon = 3;
                                                f[i+1][n4][n8][is_con][nup][ndw][ncon][now] += f[i][_4][_8][con][up][dw][nowc][la];
                                            }
                                    }
    for(int _4 = 0 ; _4 < 2 ; ++_4)
        for(int _8 = 0 ; _8 < 2 ; ++_8)
            if((!_4) || (! _8))
                for(int up = 0 ; up < 2 ; ++up)
                    for(int dw = 0 ; dw < 2 ; ++dw)
                        for(int ncon = 0 ; ncon <= 3 ; ++ncon)
                            for(int now = 0 ; now <= 9 ; ++now)
                                ans += f[11][_4][_8][1][up][dw][ncon][now];
    // printf("%lld",ans);
}

晚上顺便学习了一下整除分块这种优化。

整除分块主要是利用整除的一些性质，与分块的一些思想。

设

又

所以

也就是说对于

是相同的

而由于对于

, 不同取值不超过

个

对于

,

不同取值也不会超过

个，因此整除分块时间复杂度为

[CQOI2007]余数求和

题目描述

给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29

输入输出格式

输入格式：

两个整数n k

输出格式：

答案

输入输出样例

输入样例#1：

1
10 5

输出样例#1：

1
29

说明

30%: n,k <= 1000

60%: n,k <= 10^6

100% n,k <= 10^9

题解

因为

所以原式就是

对右边整除分块优化，时间复杂度为

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
ll n , k , ans;
int main()
{
    scanf("%lld%lld",&n,&k);
    int gx = 0;
    ans = n * k;
    for(int i = 1 ; i <= n ; i = gx + 1)
    {
        gx = k/i ? std::min(k/(k/i) , n) : n;
        ans -= (k/i) * (i + gx) * (gx - i + 1) / 2;
    }
    printf("%lld",ans);
}

那么还记得那道优美的题吗？请看#11

简述题意，对于任意小于n的x*y矩形，将它密铺成正方形所用的最小数量为v，求所有v的和。

显然变成一个正方形，边长得相等，设最小q个在x的方向，t个在y的方向，所用个数为t * q

显然当x,y约分至互质的情况时t * q最小

因此我们所求的就是

由题目数据可知，我们要么On求出1~n的所有答案O1查询，要么对于每次查询是一个线性复杂度以下的算法。

首先看分子的处理

这就是

那么我们该考虑分母的积该如何算了 , 算出来后乘上逆元即可。

我们可以最后平方

我们可以用常用的数论技巧来优化

对于

这就是

因此每次询问的答案的分母就是

最后的答案是

显然欧拉函数作为积性函数可以线性筛，并且只需要一次即可，然后从指数幂的特点来看再用前缀和来优化欧拉函数求和，这样复杂度是

这样做期望得分60

我们可以对分子的k做一个简单的根号优化

有一个著名的结论，对于

的取值不超过

个，这个就不证明了挺麻烦的，进阶指南上有。

那么我们可以对于k的指数幂一样的项一起处理，这样时间复杂度就是

补一下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
91
92
93
94
95
96
97
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define mod 19260817
#define ll long long
#define maxn 1000005
ll n , T , phi[maxn] , prime[maxn/8] , fac[maxn] , cnt;
bool inprime[maxn];
inline void euler(ll n)
{
    phi[1] = 1;
    for(ll i = 2 ; i <= n ; ++i)
    {
        if(!inprime[i]) phi[i] = i - 1 , prime[++cnt] = i;
        for(int j = 1 ; j <= cnt && i * prime[j] <= n ; ++j)
        {
            inprime[i*prime[j]] = true;
            if(!(i%prime[j])) phi[i*prime[j]] = prime[j] * phi[i];
            else phi[i*prime[j]] = phi[i] * phi[prime[j]];
            if(!(i%prime[j])) break;
        }
    }
    for(int i = 1 ; i <= n ; ++i)
        phi[i] += phi[i-1] ;
}
ll exgcd(ll a , ll b , ll& x , ll& y)
{
    if(!b)
    {
        x = 1 , y = 0;
        return a;
    }
    ll g = exgcd(b , a % b , y , x);
    y -= a/b * x;
    return g;
}
ll inv(ll k)
{
    if(!k || k == 1) return 1;
    ll x , y;
    ll g = exgcd(k,mod,x,y);
    x = (x % mod + mod) % mod;
    return x;
}
inline void pre(ll n)
{
    fac[0] = fac[1] = 1;
    for(int i = 2 ; i <= n ; ++i)
        fac[i] = fac[i-1] * i % mod;
}
inline ll pow(ll x , ll y)
{
    ll ans = 1 , base = x;
    while(y)
    {
        if(y&1) ans = ans * base % mod;
        base = base % mod * base % mod;
        y /= 2;
    }
    return ans;
}
void solve(ll n)
{
    ll ans = pow(fac[n] , 2 * n);
    ll frac = 1;
    ll gx = 0;
    for(int i = 1 ; i <= n ; i = gx + 1)
    {
        gx = n/(n/i);
        // puts("OK");
        ll pw = 2 * phi[n/i] - 1;
        // puts("OK");
        // printf("%lld %lld\n",fac[gx] , inv(fac[i-1]));
        ll base = (fac[gx] % mod * inv(fac[i-1])) % mod ;
        // puts("OK");
        // printf("pw = %lld base = %lld\n",pw,base);
        frac = frac * pow(base , pw) % mod;
        // printf("%\frac = %lld\n",frac);
    }
    printf("%lld\n",ans * inv(frac) % mod * inv(frac) % mod);
}
int main()
{
    scanf("%lld",&T);
    euler(1000000);
    pre(1000000);//the fac
    // puts("OK");
    // printf("%lld\n",fac[5] * inv(fac[3]) % mod);
    // printf("%lld\n",inv(fac[5]));
    while(T--)
    {
        scanf("%lld",&n);
        solve(n);
        // puts("OK");
    }
}