首页 > 代码库 > CH Round #54 - Streaming #5 (NOIP模拟赛Day1)解题报告
CH Round #54 - Streaming #5 (NOIP模拟赛Day1)解题报告
最近参加了很多CH上的比赛呢~Rating--了。。题目各种跪烂。各种膜拜大神OTZZZ
T1珠
描述
萌蛋有n颗珠子,每一颗珠子都写有一个数字。萌蛋把它们用线串成了环。
我们称一个数字串是有趣的,当且仅当它的第1位是2,且除了第1位以外的每一位都是3。例如,2,233,2333333都是有趣的数字串。
现在,你可以从这串珠子的任意一颗开始读,沿着顺时针或逆时针方向,到任意一颗珠子停止。这样,你就可以读出一个数字串来。
萌蛋想知道,所有能读出的有趣的数字串当中,最长的是哪一个数字串。当然,你也可能读不出任何一个有趣的数字串,你也需要对这种情况做出判断。
输入格式
输入只有一行,是一个数字串。这是从这串珠子的某一颗开始,顺时针读取恰好一圈得到的。
输出格式
输出只有一行,是能读出的最长有趣的数字串。特殊地,如果找不到任何有趣的数字串,应输出“TvT”(不含引号)。
对于每一个2的位置向右或者向左扫,每个点最多被扫到2遍,O(n)复杂度。
T2免农
萌蛋近年收入不景气,正在她发愁如何能多赚点钱时,她听到隔壁的小朋友在讨论免子繁殖的问题。(注:免子是一种简单的单细胞生物)
问题是这样的:时刻0有2只刚出生的免子。每一时刻,每只免子都会分裂成为2只免子。问时刻n共有多少只免子?
聪明的你可能已经发现,时刻n的免子数正好是第n+1个2的幂次。萌蛋不懂什么叫幂,但她也发现了规律:时刻n+1的免子数等于时刻n的免子数的2倍。前几个时刻(从0开始)的免子数依次为:
2 4 8 16 32 64 128 256 512 …
萌蛋发现越到后面免子数增长的越快,期待养免子一定能赚大钱,于是萌蛋在时刻0买了2只免子开始培养。
每天,萌蛋都要给免子们提供营养。免子的培养基非常特别,每k只免子占据一个培养基,最后剩下的不足k只占据一个培养基。由于免子特别害怕孤独,如果某个培养基只有1只免子,这只免子就会很快死掉。
然而,每个时刻的免子数仍然是可以计算的。例如,当k=7时,前几个时刻(从0开始)的免子数依次为:
2 4 7 14 28 56 112 224 448 …
给定n,你能帮助萌蛋计算时刻n她有多少只免子么?由于答案可能非常大,你只需要告诉萌蛋时刻n的免子只数对p的余数即可。
输入格式
输入只有一行,包含三个整数n k p。(n<=1,000,000,000 k,p<=1,000,000)
输出格式
输出只有一行,为一个整数,表示时刻n的免子只数对p的余数。
可以发现,如果死了一次免子,那么就再也不会死免子了。所以我们只需要找到第一次死免子的时候即可。
又可以发现,第一次死免子必定发生在前k秒内。因为免子数 Mod k只有k种可能性。免子数Mod k的结果如果在出现了重复之前没有死免子,就显然不会再死免子。
如果第i秒死了一只免子,死后还剩下l只免子则最后的答案为l*2^(n-i) mod p
复杂度 O(k+log(n))
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <map>10 #include <set>11 #include <list>12 #include <vector>13 #include <ctime>14 #include <functional>15 #define pritnf printf16 #define scafn scanf17 #define For(i,j,k) for(int i=(j);i<=(k);(i)++)18 using namespace std;19 typedef long long LL;20 typedef unsigned int Uint; 21 const int INF=0x7ffffff;22 //==============struct declaration==============23 24 //==============var declaration=================25 const int MAXN=1000010;26 LL n,k,MOD,p;27 set <LL> Exist;28 //==============function declaration============29 LL gcd(LL a,LL b);30 LL lcm(LL a,LL b);31 LL quickpow(LL a,LL Exp);32 //==============main code=======================33 int main()34 { 35 cin>>n>>k>>p; 36 MOD=p*k;37 LL fact=2;38 if (k==1){printf("0\n");return 0; }39 For(i,1,k){40 fact=fact*2;41 if (i>n) break;42 if (fact%k==1){43 fact--;44 printf("%lld\n",(fact%p*quickpow(2,n-i)%p)%p);45 46 return 0;47 }48 fact=fact%MOD;49 }50 printf("%lld\n",quickpow(2,n+1)%p);51 52 return 0;53 }54 //================fuction code====================55 LL quickpow(LL a,LL Exp)56 {57 if (Exp==0)58 return 1;59 if (Exp==1)60 return a;61 LL t=quickpow(a,Exp/2)%p;62 t=(t*t)%p;63 if (Exp&1)64 t*=a;65 return t%p;66 }67 LL lcm(LL a,LL b)68 {69 return a/gcd(a,b)*b;70 } 71 LL gcd(LL a,LL b)72 {73 return a%b==0?b:gcd(b,a%b);74 }
T3 高维网络
描述
现在有一个d维的坐标网格,其中第i维坐标的范围是[0,a_i ]。
在这个范围内建立一个有向图:我们把范围内的每个整点(每一维坐标均为整数的点)当做图上的顶点。设点A(0,0,?,0),B(a_1,a_2,?,a_d )。
对于范围内的点(x_1,x_2,?,x_d ),它会向以下这些点(如果目标点在范围内):(x_1+1,x_2,?,x_d ),(x_1,x_2+1,?,x_d ),?,(x_1,x_2,?,x_d+1)连有向边。
现在从点A到点B会有若干条路径,路径的条数可以十分简单地算出。然而不幸的是,范围内有p个点被破坏了(点A和点B不会被破坏),其中第i个点的坐标为(x_(i,1),x_(i,2),?,x_(i,d) )。你需要算出从点A到点B剩余的路径条数。
由于答案可能很大,你只需要输出它对1,000,000,007取模的结果。
输入格式
第一行为两个整数d p。
第二行为d个整数,其中第i个数是a_i。
接下来p行,每行d个整数,其中第i行第j个数是x_(i,j)。
输出格式
一个整数,表示从点A到点B剩余的路径条数对1,000,000,007取模的结果。
简单来说就是一个d维的点,从(0,0......0,0)走到(A1,A2....Ad-1,Ad),每走一次只能是一个坐标+1,其中有P个点不能经过,问有多少种方法。
首先要知道在P=0的时候,从A到B走法的计算方法如下:
path(A,B)=(A1+A2+A3+...+Ad)!/(A1!A2!A3!..Ad!)
是不是很眼熟= =跟重复元素的排列公式一模一样。
从A点到B点,你要将每一维的坐标都增加Ai,就是增加方式的一种排列,所以有path(A,B)种办法。
记从A到X点不经过任何一个破坏点的方法为dp[x]
则dp[x]=path(A,X)-∑dp[Y]*path(Y,X)
应该是很好理解的吧。。
那么考虑实现问题。
事先处理好所有数的阶乘%10000000007的值以及逆元
阶乘暴力算就行。逆元拓展欧几里得或者快速幂
时间复杂度O(d*p^2)但是各种常数项有点大
#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <queue>#include <stack>#include <map>#include <set>#include <list>#include <vector>#include <ctime>#include <iterator>#include <functional>#define pritnf printf#define scafn scanf#define For(i,j,k) for(int i=(j);i<=(k);(i)++)using namespace std;typedef long long LL;typedef unsigned int Uint; const int INF=0x7ffffff;//==============struct declaration==============//==============var declaration=================const int MAXN=510;const int MOD=1000000007;int A[MAXN],d,p;LL f[MAXN];LL factor[10000001];vector <int> Points[510];//==============function declaration============LL quickpow(int a,int Exp);LL inv(int a);LL path(vector <int>&P1,vector <int> &P2);void fact();//==============main code=======================int main(){ #define FILE#ifdef FILEfreopen("input.txt","r",stdin);freopen("output.txt","w",stdout);#endifscanf("%d%d",&d,&p);For(i,1,d)scanf("%d",&A[i]);For(i,1,p){int v;Points[i].clear();For(j,1,d){scanf("%d",&v);Points[i].push_back(v);}}For(i,1,d){Points[0].push_back(0);Points[p+1].push_back(A[i]);}sort(Points,Points+p+2);fact();memset(f,0,sizeof(f));for(int i=1;i<=p+1;i++){f[i]=path(Points[0],Points[i]);//cout<<f[i]<<endl;for(int j=1;j<=i-1;j++)f[i]=(f[i]-(f[j]*path(Points[j],Points[i])))%MOD;while (f[i]<MOD){f[i]+=MOD; }f[i]%=MOD;} printf("%d\n",f[p+1]);return 0;}//================fuction code====================LL quickpow(int a,int Exp){if (Exp==0) return 1;if (Exp==1) return a;LL t=quickpow(a,Exp/2);t=(t*t)%MOD;if (Exp&1)t=(t*a)%MOD;return t;}LL path(vector <int>&P1,vector <int> &P2){LL res=1,up=0;For(i,0,d-1)if (P1[i]>P2[i])return 0;For(i,0,d-1){up=(up+(P2[i]-P1[i]))%MOD;res=(res*inv(factor[P2[i]-P1[i]]%MOD))%MOD;}res=(res*factor[up]%MOD)%MOD;return res;}void fact(){LL res=1;factor[0]=1;for (int i=1;i<10000001;i++){res=(res*i)%MOD;factor[i]=res;}return;}LL inv(int a){return quickpow(a,MOD-2);}
蒟蒻居然这么水的题目只有110分QAQ
准备NOIp三等滚粗了OTZZZZZZ
CH Round #54 - Streaming #5 (NOIP模拟赛Day1)解题报告