当前位置：首页 > news >正文

CH Round #54 - Streaming #5 (NOIP模拟赛Day1)解题报告

news 来源：原创 2024/5/2 8:35:26

最近参加了很多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 printf
16 #define scafn scanf
17 #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 }

T2代码

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）=(A₁+A₂+A₃+...+A_d)!/(A₁!A₂!A₃!..A_d!)

是不是很眼熟= =跟重复元素的排列公式一模一样。

从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 FILE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
scanf("%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);
}