lemonoil


OI__nothing is impossible


数论专题

第一道题题意不明,1.5h,100分。。。无语。

单峰数列

这里写图片描述 这里写图片描述

题解

单峰数列 我们从大到小放,除最大数以外每一个数只能放在前面放的所有数的最左边或最右边. 于是去除单调递增单调递减重复计算,答案为2^n-2,特判n = 1 和p = 1.

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define PROB "sequence"
typedef unsigned long long qword;
qword times_mod(qword x,qword y,qword mod)
{
qword ret=0;
while (y)
{
if (y&1)ret=(ret+x)%mod;
x=(x+x)%mod;
y>>=1;
}
return ret;
}
qword pow_mod(qword x,qword y,qword mod)
{
qword ret=1%mod;
while (y)
{
if (y&1)
ret=times_mod(ret,x,mod);
x=times_mod(x,x,mod);
y>>=1;
}
return ret;
}
int main()
{
freopen(PROB".in","r",stdin);
freopen(PROB".out","w",stdout);
qword n,mod;
while (~scanf("%I64u%I64u",&n,&mod))
{
if (n==1)
{
printf("%I64u\n",1%mod);
continue;
}
qword ans=pow_mod(2,n,mod)-2;
ans=(ans+mod)%mod;
printf("%I64u\n",ans);
}
}

数学题(裸题)

这里写图片描述 这里写图片描述

题解

题意:已知B,A%p,求(A/B)%p. 设A B ans (mod p) 原问题变成了已知B ans mod p 求ans. 我们直接套用拓展欧几里得算法模板. B ans + k p = n 由于保证gcd 为1,所以ans 在p 内只有一个解.

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long qword;
qword ext_gcd(qword a,qword b,qword &x,qword &y)
{
if (a%b==0)
{
//a*x+b*y==b
x=0;y=1;
return y;
}
qword ret=ext_gcd(b,a%b,x,y);
qword tx=x,ty=y;
x=ty;
y=tx-a/b*ty;
return ret;
}
qword pow_mod(qword x,qword y,qword mod)
{
qword ret=1;
while (y)
{
if (y&1)ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
int main()
{
int nn;
freopen("calc.in","r",stdin);
freopen("calc.out","w",stdout);
scanf("%d",&nn);
while (nn--)
{
qword n,b;
qword p;
scanf("%I64d%I64d%I64d",&n,&b,&p);
//n=A%9973
//n=b*d%9973
//n=b*d+9973*k
qword d0,k0;
//d0=pow_mod(b,9971,9973);
ext_gcd(b,p,d0,k0);
d0=d0*n%p;
d0=(d0+p)%p;
printf("%I64d\n",d0);
}
}

定情信物(bzoj 3823)

这里写图片描述 Description 都说程序员找不到妹子,可是无人知晓,三生石上竟然还刻着属于小 E 的一笔。 那一天,小 E 穷尽毕生的积蓄,赠与了妹子一个非同寻常的定情信物。那是一个小小的正方体,但透过它,可以看到过去,可以洞彻天机。 这份信物仿佛一只深邃的眼。当看透它看似简单的外表后,深邃的内心却最是可以叩击人的灵魂的。不出所料,妹子果然被这个信物超越空间的美所吸引。 “易有太极,是生两仪,两仪生四象,四象生八卦。,八卦定吉凶,吉凶生大业。” 这句箴言在其上得到了完美的诠释。是的,这正是一个超正方体。 小 E 告诉妹子,他的情意也如这份信物一样深厚。现在妹子想知道,小 E 对她的情意究竟有几分? 我们知道,点动成线,线动成面,面动成体......即 n 维超立方体可看作由 n-1 维超立方体沿垂直于它的所有的棱的方向平移得到的立体图形。我们可以将点看作 0 维超立方体,将直线看作 1 维超立方体,将正方形看作 2 维超立方体......依此类推。 任何一个 n 维超立方体(n>0)都是由低维的超立方体元素组成的:它的 n-1 维表面是 n-1 维的超立方体,它的 n-2 维边缘是 n-2 维的超立方体,它的 n-3 维元素是 n-3 维的超立方体...... 小 E 对妹子的情意即为在他的定情信物——K 维超立方体中,含有每一维的元素个数。由于元素个数可能较大,只需要输出它所包含的每一维元素个数模 P 后的异或和。 Input 两个整数 K、P,详见题目叙述。 Output 一个非负整数,表示小 E 的定情信物所包含的每一维元素个数模 P 后的异或和。注意:异或和可能会大于 P。

Sample Input input 1 3 7 Input 2 4 2333 Input 3 12 7723 Sample Output Output1 3 Output 2 33 Output 3 360

Hint 对于样例2的解释: 一个三维超立方体含有 8 个零维元素、12 个一维元素、6 个二维元素、1 个三维元素,模 7 后分别为 1,5,6,1,异或和为 1^5^6^1=3。 对于 100%的数据,N≤10^7,P 为 10^9 内的素数。

题解

找规律可得:\(a_i = C(n,i)2_{n-i}\) 脑补也很容易能把规律推出来,一个n 维超正方体有n 个维度,那么要确定其中的一个k 维元素,就是在这n 个维度中选择k 个维度,个数\(C(n,k)\),剩下\(n-k\)个维度可以任意平移,所以再乘\(2^{n-k}\)于是下一步就是如何求ai,直接扫一遍,将答案表示成//(t*p^k//),存下了t,k就存下了答案,线性筛预处理处逆元,分别推出\(C(n,i)\),\(2^i\),乘起来再异或就是答案了。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cassert>
using namespace std;
#define MAXN 11000000
typedef long long qword;
int inv[MAXN];
int prime[1100000],topp=-1;
bool pflag[MAXN];
qword n,p;
qword pow_mod(qword x,qword y)
{
qword ret=1;
while (y)
{
if (y&1)ret=ret*x%p;
x=x*x%p;
y>>=1;
}
return ret;
}
void init()
{
inv[1]=1;
for (int i=2;i<=n;i++)
{
if (!pflag[i])
{
prime[++topp]=i;
inv[i]=pow_mod(i,p-2);
}
for (int j=0;j<=topp && (qword)i*prime[j]<MAXN;j++)
{
pflag[i*prime[j]]=true;
inv[i*prime[j]]=(qword)inv[i]*inv[prime[j]]%p;
if (i%prime[j]==0)break;
}
}
}
int main()
{
freopen("cube.in","r",stdin);
freopen("cube.out","w",stdout);
scanf("%I64d%I64d",&n,&p);
qword x,y,z;
int i,j,k;
qword ans=0;
init();
x=1;y=1;
ans^=x*y%p;
int totp=0;
for (i=1;i<=n;i++)
{
x=x*2%p;
z=n-i+1;
while (z%p==0)totp++,z/=p;
y=y*z%p;
z=i;
while (z%p==0)totp--,z/=p;
y=y*inv[z%p]%p;
ans^=totp?0:x*y%p;
}
printf("%I64d\n",ans);
}

click it and link me

Launch CodeCogs Equation Editor