关键词：
题意：给你三个杯子，一开始钥匙放在中间的杯子里，然后每一回合等概率将左右两个杯子中的一个与中间杯子交换。求n回合之后钥匙在中间杯子的概率。这里要求概率以分数形式输出，先化成最简，然后对1e9 + 7取模。
题解：首先我们可以轻易得到一个递推式：$ d[i] = frac{{1 - d[i - 1]}}{2} $
但递推式是不行的，我们要得到一个封闭形式。
运用数列技巧，我们可以进行如下变换：$d[i] - frac{1}{3} = - frac{1}{2}(d[i - 1] - frac{1}{3})$
那么我们有 $d[n] = frac{{{{( - 1)}^n} + {2^{n - 1}}}}{{3 imes {2^{n - 1}}}}$
其中我们发现，${{{( - 1)}^n} + {2^{n - 1}}}$ 一定是3的倍数，且商一定是奇数，所以与剩下部分互质
也即 $p = frac{{{{( - 1)}^n} + {2^{n - 1}}}}{3}$ $q = {2^{n - 1}}$
带进去算就好了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define mod 1000000007 5 6 inline LL read() { 7 LL x = 0, f = 1; char a = getchar(); 8 while(a < ‘0‘ || a > ‘9‘) { if(a == ‘-‘) f = -1; a = getchar(); } 9 while(a >= ‘0‘ && a <= ‘9‘) x = x * 10 + a - ‘0‘, a = getchar(); 10 return x * f; 11 } 12 13 int n, p = 2, q, f = 1; 14 15 inline int fpow(int x, LL k) { 16 int ret = 1; 17 while(k) { 18 if(k & 1) ret = 1LL * ret * x % mod; 19 k /= 2; x = 1LL * x * x % mod; 20 } 21 return ret; 22 } 23 24 int main() { 25 n = read(); 26 LL tmp; int inv2 = fpow(2, mod -2), inv3 = fpow(3, mod - 2); 27 for(int i = 1; i <= n; i++) { 28 tmp = read(); 29 f = 1LL * f * tmp % 2; 30 p = fpow(p, tmp); 31 } 32 q = 1LL * p * inv2 % mod; 33 p = 1LL * (q + (f ? -1 : 1)) * inv3 % mod; 34 printf("%d/%d " ,p ,q); 35 return 0; 36 }
bzoj_5301_[cqoi2018]异或序列&&cf617e_莫队
Description已知一个长度为n的整数数列a[1],a[2],…,a[n]，给定查询参数l、r，问在[l,r]区间内，有多少连续子序列满足异或和等于k。也就是说，对于所有的x，y(l≤x≤y≤r)，能够满足a[x]^a[x+1]^…^a[y]=k的x，y有多少组。Input输... 查看详情
agc006c&cf1110e(代码片段)
这两个题都有一个公用的小trick，所以我就写一起了！AGC006C题目叙述一些兔子站在坐标轴上，兔子的坐标为(x_1,x_2,cdots,x_n)。第(i)只兔子会这样跳跃：随机等概率选择相邻两个兔子之一，以那只兔子为中心，跳到对称的另一边。... 查看详情
bzoj4424:cf19efairy&&codeforces19e.fairy树形dp(代码片段)
参考：https://blog.csdn.net/heheda_is_an_oier/article/details/51131641这个找奇偶环的dp1真是巧妙，感觉像tarjan一样首先分情况讨论，如果没有奇环，每条边都可以删；如果有一个奇环，奇环上隋边山；否则，删被所有奇环覆盖且没被任何一... 查看详情
做题cf196e.openingportals排除无用边&最小生成树(代码片段)
题意：给出一个有(n)个结点，(m)条边的连通无向图，边有边权，等于经过这条边所需的时间。有(k)个点设有传送门。一开始，所有传送门关闭。你从(1)号点出发，每当你到达一个有传送门的点，那个传送门就会永久开启。你可以... 查看详情
cf1076e：vasyaandatree（dfs&差分）(代码片段)
Vasyahasatreeconsistingofn nverticeswithrootinvertex1 1.Atfirstallverticeshas0 0writtenonit.Letd(i,j) d(i,j)bethedistancebetweenverticesi iandj j,i.e.numberofedgesinthesh 查看详情
cf1039dyouaregivenatree&&cf1059esplitthetree的贪心解法
1039D题意：给你一棵树，要求对给定链长于k=1,2,3,...,n，求出最大的链剖分。1059E题意：给你一棵带权树，要求对于一组给定的L,W求出最小完全竖链剖分满足每条链点数不超过L，权值和不超过W。显然两题是有共同点的，就是让我... 查看详情
cf552e.twoteams(代码片段)
...);i++)#definerepp(i,a,b)for(inti=(a);i>=(b);--i)#defineRI(n)scanf("%d",&(n))#defineRII(n,m)scanf("%d%d",&n,&m)#defineRIII(n,m,k)scanf("%d%d%d",&n,&m,&k)#defineRS(s)scanf("%s",s);#definelllonglong#defineREP(i,N)for(inti=0;i<(N);i++)#defineCLR(A,v)m 查看详情
cf715c&&cf716edigittree点分治(代码片段)
题目大意给出一个树，每条边上写了一个数字，给出一个G，求有多少条路径按顺序读出的数字可以被G整除。保证G与10互质。题解双倍经验~首先一条路径顺着读和逆着读是视为两条不同的路径的，即使值一样。同时要注意一条路... 查看详情
cf484esignonfence&&[国家集训队]middle(代码片段)
CF484ESignonFence#include<bits/stdc++.h>#defineRGregister#defineILinline#define_100100#defineinf1e9+7usingnamespacestd;ILintgi()RGintdata=0,m=1;RGcharch=0;while(ch!='-'&&(ch< 查看详情
cf1066a&b&c(代码片段)
A题目链接CF1066AVovaandTrain思路:类似前缀和暴力搞一下code:#include<bits/stdc++.h>usingnamespacestd;intT,L,V,l,r;template<typenameT>inlinevoidread(T&t);intmain()scanf("%d",&T);while(T- 查看详情
cf914gsumthefibonacci快速？？变换模板
【CF914G】SumtheFibonacci题解：给你一个长度为n的数组s。定义五元组(a,b,c,d,e)是合法的当且仅当：1.$1lea,b,c,d,elen$2.$(s_a|s_b)&s_c&(s_d$^$s_e)=2^i$，i是某个整数3.$s_a&s_b=0$求$sumf(s_a|s_b)*f(s_c)*f(s_d$^$s_e)$，f是斐波那契数列， 查看详情
cf444e.dzylovesplanting(代码片段)
?????????amp tin opera print pre [1] http putchar cti 查看详情
cf696cplease(代码片段)
矩阵快速幂+扩展欧拉定理对于一个矩阵(A)，我们有(A^nequivA^n\%phi(m)+phi(m)(\%m))经过简单的列举或推导可得设目前进行了(x)轮，(f(x))为分子，(g(x))为分母则有(f(x)=g(x-1)-f(x-1),g(x)=2g(x-1))由此及首项可得(x>1)时概率的分子一直是奇数，... 查看详情
题解cf#983e-nncountry(代码片段)
...，我们可以直接倍增获得答案，所以以下讨论均为u!=lca&&v!=lca的情况。若在节点u和 查看详情
[cf1539e]gamewithcards(代码片段)
...点进行\\(\\rmDP\\).何为交换点？比如\\[\\beginmatrix\\colorred0&0&0&0&0&\\colorred1&1&1&am 查看详情
cf1527dmextree(mex&树&容斥)(代码片段)
CF1527DMEXTree(mex&树&容斥)考虑简单容斥，meximex_imexi等于包含[0,i−1][0,i-1][0,i−1]的所有路径减取包含[0,i][0,i][0,i]的路径。记录：ansians_iansi为包含[0,i][0,i][0,i]的所有路径。mexi=ansi−1−ansimex_i=ans_i-1-a 查看详情
aizu2249&cf449b
Aizu2249&cf449B1、Aizu-2249选的边肯定是最短路上的。如果一个点有多个入度，取价值最小的。#include<bits/stdc++.h>usingnamespacestd;#definefifirst#definesesecond#definempmake_pair#definepbpush_back#definerep(i,a,b)for(inti=(a 查看详情
cf1592eboredbakry(代码片段)
CF1592EBoredBakry题意：给你长度为n的数组a，现在定义一段区间[l,r]为good，如果al&al+1&...&ar>al⊕al+1⊕...⊕ara_l\\&a_l+1\\&...\\&a_r>a_l⊕a_l+1⊕...⊕a_r 查看详情