Post 28

Veröffentlicht am | Edited on

[SDOI2010]古代猪文

题目背景

“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”

——选自猪王国民歌

很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄园经济，很少与外界联系，商贸活动就更少了。因此也很少有其他动物知道这样一个王国。

猪王国虽然不大，但是土地肥沃，屋舍俨然。如果一定要拿什么与之相比的话，那就只能是东晋陶渊明笔下的大家想象中的桃花源了。猪王勤政爱民，猪民安居乐业，邻里和睦相处，国家秩序井然，经济欣欣向荣，社会和谐稳定。和谐的社会带给猪民们对工作火红的热情和对未来的粉色的憧憬。

小猪iPig是猪王国的一个很普通的公民。小猪今年10岁了，在大肥猪学校上小学三年级。和大多数猪一样，他不是很聪明，因此经常遇到很多或者稀奇古怪或者旁人看来轻而易举的事情令他大伤脑筋。小猪后来参加了全猪信息学奥林匹克竞赛(Pig Olympiad in Informatics, POI)，取得了不错的名次，最终保送进入了猪王国大学(Pig Kingdom University, PKU)深造。

现在的小猪已经能用计算机解决简单的问题了，比如能用P++语言编写程序计算出A + B的值。这个“成就”已经成为了他津津乐道的话题。当然，不明真相的同学们也开始对他刮目相看啦~

小猪的故事就将从此展开，伴随大家两天时间，希望大家能够喜欢小猪。

题目描述

猪王国的文明源远流长，博大精深。

iPig在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为N。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。

iPig打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的k分之一，其中k是N的一个正约数（可以是1和N）。不过具体是哪k分之一，以及k是多少，由于历史过于久远，已经无从考证了。

iPig觉得只要符合文献，每一种能整除N的k都是有可能的。他打算考虑到所有可能的k。显然当k等于某个定值时，该朝的猪文文字个数为N / k。然而从N个文字中保留下N / k个的情况也是相当多的。iPig预计，如果所有可能的k的所有情况数加起来为P的话，那么他研究古代文字的代价将会是G的P次方。

现在他想知道猪王国研究古代文字的代价是多少。由于iPig觉得这个数字可能是天文数字，所以你只需要告诉他答案除以999911659的余数就可以了。

输入输出格式

输入格式：

输入文件ancient.in有且仅有一行：两个数N、G，用一个空格分开。

输出格式：

输出文件ancient.out有且仅有一行：一个数，表示答案除以$999911659$的余数。

输入输出样例

输入样例#1：

1
4 2

输出样例#1：

1
2048

说明

数据规模

100%的数据中，$1 <= G <= 1000000000，1 <= N <= 1000000000$。

题解

自从联赛前一个多月到现在，好久没有写过数学题了。

所以调了一年

让我先把一堆bug表出来。

img

显然这样子处理阶乘的逆元虽然慢一点但绝对不会错！

img

取模漏掉等号可还行？

先说这么多吧。

题意让你求

$G^{\sum_{d|n}C_{n}^{d}}$

显然要用到欧拉定理处理上面的指数。

对于$mod-1$，我们发现可以把它拆成小质数的乘积（这也是本题唯一的难点吧233）

然后就可以对每个小质数都应用卢卡斯定理进行计算，然后CRT合并即可。

感觉还没EXLUCAS的板子难

分析时间复杂度：
考虑到模数分解的4个小质数都要计算，是一个常数4,。对于每次计算，我们需要$O(\sqrt{n})$的枚举其约数，然后对于每个约数，用卢卡斯定理$O(plog_pn)$算出其值。

可以分析得到这就是整个程序的渐进复杂度，为$O(4\sqrt{n}plog_pn)$

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#define LL long long
const int mod = 999911659;
LL n , h , f[50005] , g[50005];
int fac[10] , tot;

void exgcd(int a , int b , int& x , int& y)
{
    if(!b) x = 1 , y = 0;
    else exgcd(b , a % b , y , x) , y -= a/b * x;
}

inline int inv(int a , int modm)
{
    int x , y;
    exgcd(a , modm , x , y);
    x = (x % modm + modm) % modm;
    if(!x) x += modm;
    return x;
}


inline void pre(int k)
{
	f[0] = 1;
	g[0] = inv(1, k);
	for(int i = 1 ; i <= k ; ++i)
		f[i] = 1ll * i * f[i-1] % k , g[i] = g[i-1] * inv(i , k) % k;
}


inline LL C(int n , int m , int p)
{
    if(m > n) return 0;
    LL ans = 1;
	ans = f[n] * g[m] % p * g[n-m] % p;
    return ans;
}

LL lucas(int n , int m , int p)
{
    if(!m) return 1;
    return C(n % p , m % p , p) * lucas(n / p , m / p , p);
}

inline void getFac()
{
    int lim = std::sqrt(mod - 1) , tmp = mod - 1;
    for(int i = 2 ; i <= lim ; ++i)
    {
        if(tmp % i == 0)
        {
            ++tot;
            fac[tot] = i;
            while(tmp % i == 0) tmp /= i;
        }
    }
    if(tmp > 1) fac[++tot] = tmp;
}

inline LL calc(int modm)
{
    LL ans = 0;
    for(int i = 1 ; i * i <= n ; ++i)
    {
        if(n % i == 0)
        {
            (ans += lucas(n , i , modm)) %= modm;
            if(n != i * i) (ans += lucas(n , n/i , modm)) %= modm;
        }
    }
    return ans;
}

inline LL CRT(LL x , LL nowm){
    return x * ((mod-1)/nowm) * inv((mod-1)/nowm , nowm);
}
inline LL solve()
{
    LL ans = 0;
    getFac();
    for(int i = 1 ; i <= tot ; ++i)
    {
        int nowm = fac[i];
		pre(nowm);
        (ans += CRT(calc(nowm) , nowm)) %= (mod - 1);
	}
    return ans;
}

inline LL pow(LL x , LL y , LL m)
{
    LL ans = 1 , base = x;
    for( ; y ; (base *= base) %= m , y >>= 1)
        if(y & 1)
            ans = ans * base % m;
    return ans;
}

int main()
{
    scanf("%lld%lld",&n,&h);
    if(h % mod == 0){
      	  puts("0");
    	  return 0;
    }
    printf("%lld\n",pow(h,solve(),mod));
}

「一本通 2.1 练习 8」收集雪花

题目描述

不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来，作为礼物送给在南方的同学们。一共有 nn 个时刻，给出每个时刻下落雪花的形状，用不同的整数表示不同的形状。在收集的过程中，同学们不希望有重复的雪花。你可以从任意 aa 时刻开始，在 bb 时刻停止。aa 到 bb 时刻中间的雪花也都将被收集。他们希望收集的雪花最多。

输入格式

第一行一个正整数 nn；

第 22 行 nn 个非负整数表示 nn 个时刻雪花的形状。

输出格式

最多能收集雪花的数量。

样例

输入样例

1
2
5
1 2 3 2 1

输出样例

1
3

数据范围与提示

对于 97 分的数据，$1\le n \le 10^6, 0\le x_i \le 10^8$（为原始数据）

应用户要求，加入 3 分的数据，$1\le n\le 10^6,0\le x_i\le 10^9$

题解

这种连续区间问题很容易想到双指针来做啦。

就是只要没出现，右指针就一直向右扩展，当一个元素出现过时，就向右移动左指针，应该算是一种贪心思想吧。

这道题就是这么简单啦。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1000005
#define maxv 1000000005
int n , a[maxn] , ans;
bool cur[maxv];
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i]);
	int L = 1 , R = 2 , cans = ans = 1;
	cur[a[1]] = true;
	while(R < n)
	{
		if(!cur[a[R]]) cur[a[R]] = true , ++cans , ++R;
		else cur[a[L]] = false , ++L , --cans;
		ans = std::max(ans , cans);
	}
	printf("%d\n",ans);
}

这个快速算阶乘挺有意思（注意用完这个函数还得把那些pi质因子乘回去！）

1
2
3
4
5
6
7
8
9
10
11
12
13
inline LL fac(LL n , LL pi , LL pk)
{
    if(!n) return 1;
    LL ans = 1;
    if(n / pk){
        for(int i = 2 ; i <= pk ; ++i)
            if(i % pi) (ans *= i) %= pk;
        ans = pow(ans , n / pk , pk);
    }
    for(int i = 2 ; i <= n % pk ; ++i)
        if(i % pi) (ans *= i) %= pk;
    return ans * fac(n / pi , pi , pk) % pk;
}

「SHOI2015」超能粒子炮・改

题目描述

曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明：超能粒子炮・改——一种可以发射威力更加强大的粒子流的神秘装置。

超能粒子炮・改相比超能粒子炮，在威力上有了本质的提升。它有两个参数 nn、kk，它会向每个编号为 00 到 kk（包含两端）的位置 ii 发射威力为 \mathrm{C}_n^i \mathbin{\mathrm{mod}} 2333Cnimod2333 的粒子流。

现在 SHTSC 给出了他的超能粒子炮・改的参数，让你求出其发射的粒子流的威力之和除以 23332333 所得的余数。

输入格式

第一行一个整数 tt 表示数据组数。
之后 tt 行，每行两个整数 nn、kk，含义如题面描述。

输出格式

tt 行，每行一个整数，表示其粒子流的威力之和模 23332333 的值。

样例

样例输入

1
2
3
4
3
5 5
10 7
1145 14

样例输出

1
2
3
32
968
763

数据范围与提示

$t = 100000，n, k \leq 10^{18}$。

题解

题意就是说求出

$\sum_{i=0}^{k}C_n^i$

这题好像除了用整除分块的思想外没有其他很好的方法。。

直接上其他人的题解就得了。

img

img

由于我突然想咕掉代码，所以明天底下会补上代码，今天就此结束。

End.