第一道题题意不明,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) { 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); qword d0,k0; 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); }
|