前两天打了第二场积分赛,难度明显比上次高,感觉更考验思维了,收集了一些我认为有价值的题目,因为太懒了,不想自己写思路题解了,搬来了别人的代码和题解,以后争取养成保存代码的习惯🐷
A 徐半仙的数学难题
描述
徐半仙经常修炼。但是每次修炼所能提升的功力确是不确定的(可能是功力还不够深厚
吧)。
每次修炼结束之后,徐半仙的脑海中就会浮现出两个数字,n和m,他的师父跟他说他每
次修炼增加的功力就是由这两个数决定的。每次增加的功力为(n!!!)%m,即n的阶乘的阶乘的
阶乘对m取模之后的值。
徐半仙想让你帮他写一个程序,通过n和m得到他每次修炼之后提升了多少功力。如果这
次修炼后提升的功力为0,输出baigei
输入数据
多组输入,第一行一个正整数t(1 ≤ t ≤ 105)表示数据组数
每组数据包含两个整数n, m(0 ≤ n ≤ 109, 1 ≤ m ≤ 109)
输出数据
对于每组数据,如果答案为0,输出baigei,否则输出答案(每次修炼后提升的功力)
样例输入
样例输出
提示
在样例中,(2!!!) = 2,对6553取模为2,直接输出,对2取模为0,输出baigei
分析
我们知道模最大是109,并且很容易知道从4开始,这个数的阶乘的阶乘已经是大于109的,
并且因为我们求的是阶乘,阶乘最后取模和每次取模后相乘的结果相同,因为现在计算的数一
定大于模,所以一定会出现一项为0,因此最后的结果也为0。所以如果n小于4,我们直接暴力
计算就可以了,反之直接输出baigei即可
CODE
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
| #include <bits/stdc ++.h> using namespace std; typedef long long ll; #define pb push_back #define mp make_pair const int maxn = 1e5 +10; const int mod = 1e9 +7; const int INF = 0 x3f3f3f3f ; int main () { int t; cin >>t; while(t--){ ll n,m,ans; cin >>n>>m; if(n <=1){ ans =1%m; }else if(n==2){ ans =2%m; }else if(n==3){ ans=1; for(ll i=1;i <=720;i++){ ans *=i; ans %=m; } }else{ ans =0; } if(ans ==0){ cout <<"baigei\n"; }else{ cout <<ans <<endl; } } return 0; }
|
B 徐半仙的八字谜盘
有一天徐半仙正在街道上给人算八字,他摆弄一个棋盘,和K个棋子,棋盘是N × N的矩阵方
格图,共有N × N个格子。
突然一位神秘ACM大佬来了,对徐半仙说:大仙,是不是您什么难题都算得出来啊?
徐半仙:Of course!
ACM大佬:那你算算这N × N的棋盘,每个方格只能放一个棋子,要把K个棋子都放进去,并且
第一行,最后一行,第一列,最后一列,主对角线,副对角线都至少有一颗棋子的方案数是多
少?
顿时,徐半仙冷汗直流,不知如何应对这位不速之客,只好说:ok….ok…..
为了不显尴尬,徐半仙偷偷用他的迷你手机给你发了一通电报,告诉你N和K,请求你尽快把答
案发送给他。
第一行为数据的组数T (T ⩽ 1000)
接下来T行,每行为两个整数N和K (2 ⩽ N ⩽ 100, 0 ⩽ K ⩽ 100)
输出T行,第i行为第i组询问的答案。由于答案可能过大,请将答案模1e9+7之后再输出。
分析
这题主要考察了组合数+容斥原理,其中组合数不是难点,直接套模板就行。
这里如果直接求就必须得考虑很多的情况,所以可以反着来,先求个无规则的任意的摆放数,
再从这个总数里面减去不符合规则的。
但是我们发现,如果减去了第一行没有棋子的摆放数A,再减去了最后一行没有棋子的摆放数B,
其实就多减去了第一行和最后一行没有棋子的情况,所以这一部分减多的,还要加回来。这里
就可以看到容斥原理了,然后就可以写一个二进制枚举,一共就6条线上的格子,2的6次方种
情况,对应0~31(1代表该条线上没有棋子,0代表可有可无),如果是奇数个1就减去对应的摆
放数,如果是偶数个1,就加上对应的摆放数。代码稍微多点,但思路上并不难。
CODE
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
| #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MAXN=10010; const ll MOD=1e9+7; ll c[MAXN][110]; void __initC(ll N = 10005){ c[1][1]=1; for(ll i=0;i<=N;i++) c[i][0] = 1; for(ll i=1;i<=N;i++){ for(ll j =1;j<=105;j++){ c[i][j]=(ll)(c[i-1][j]+c[i-1][j-1])% MOD; } } } ll N,K; int main() { __initC(); ll t; scanf("%lld",&t); while(t--){ scanf("%lld%lld",&N,&K); ll ans=0; for(ll i=0;i<(1<<6);i++){ ll cnt=0,n=N,m=N,L=0,R=0; for(ll j=0;j<6;j++){ if(i>>j &1){ cnt++; if(j==0||j==1) n--; if(j==2||j==3) m--; if(j==4){ L=N; if((i>>0&1)||(i>>2&1)) L--; if((i>>1&1)||(i>>3&1)) L--; } if(j==5){ R=N; if((i>>0&1)||(i>>3&1)) R--; if((i>>2&1)||(i>>1&1)) R--; } } } ll num=n*m; if(L && R && N&1) num-=L+R-1; else num-=L+R; if(cnt&1) ans=(ans-c[num][K]+MOD)%MOD; else ans=(ans+c[num][K])%MOD; } printf("%lld\n",ans); } return 0; }
|
D 徐半仙的修仙之路
徐半仙每天闲来无事就在家中打坐,他相信这样能够悟道,得道升仙的方法;
有一天他接到了一个电话,电话中告诉他,蜀山的掌门给了他一次让他去蜀山学习的机会,约
他去城郊见面。于是他特别开心的答应了下来,但是他到了以后发现对方竟然是传销团伙,徐
半仙这时十分的后悔,他想偷偷的逃走但是这里守卫森严他一点办法都没有,这时他十分无助
的哭泣着并且十分后悔自己迷恋修仙。忽然旁边的憨憨龙告诉他,只要你能够计算出这个房子
有几间房间,并且最大的一间房间有多大就可以帮助他逃走了。
这个房子是只有一层,被分成了n行m列,每一间房间的面积都是1,但是因为传销团伙
为了节约空间,这些房间的四面墙有些被堵着了。并且如果两个房间连在一起就是一个面积
为2的房间。
这时徐半仙突然看到了机会,于是经过徐半仙的一波神奇的操作后他和憨憨龙一起逃出了
这个传销团伙,并且还配合警方抓捕了这个传销团伙。从这以后徐半仙再也不想着修仙了,他
一心专注于程序设计,并成为了一名优秀的acmer。
聪明的你一定想知道徐半仙如何计算的吗?那么你也来尝试一下吧,看看你和徐半仙谁更
厉害一点!
每个测试有T组数据每组第一行输入两个数 n, m (1 ⩽ n, m ⩽ 50。接下来n行数据,每
行m个整数这个整数p表示表示这个房间所拥有的墙的编号和 (1表示左墙,2表示上墙,4表示
右墙,8表示下墙)
输出两个整数分别代表房间的数量,和最大的房间面积。
1 2 3 4 5 6 7 8 9 10 11
| >1
>4 7
>11 6 11 6 3 10 6
>7 9 6 13 5 15 5
>1 10 12 7 13 7 5
>13 11 10 8 10 12 13
|
分析
这题主要考察你的dfs和你的建模能力。其实如果就是我们的一个模板题Oil Deposits
只是在这道题上加了一个走下一步的限制条件。
如果 p&8 == 0 我们可以向下走
如果 p&4 == 0 我们可以向右走
如果 p&2 == 0 我们可以向上走
如果 p&1 == 0 我们可以向左走
这样的话就和上面的模板题一样了
CODE
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
| #include<bits/stdc++.h> using namespace std; int maze[60][60],M,N; int book[60][60]; int roomnum =0, maxroom =0, room; void dfs(int x,int y){ if(book[x][y]) return; room++; book[x][y]=1; if(( maze[x][y] & 1)==0) dfs(x,y-1); if(( maze[x][y] & 2)==0) dfs(x-1,y); if(( maze[x][y] & 4)==0) dfs(x,y+1); if(( maze[x][y] & 8)==0) dfs(x+1,y); } int main () { int t;cin>>t; while(t--){ cin>>M>>N; memset(book ,0,sizeof(book )); for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ cin>>maze[i][j]; } } for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ if(!book[i][j]){ room=0; roomnum++; dfs(i,j); maxroom=max(maxroom,room ); } } } cout<<roomnum<<" "<<maxroom<<"\n"; } return 0; }
|
G 徐半仙的数学问题
已知有a,b,c,d四个正整数求满足下列两个等式的x的个数。
gcd (x, a) = b
lcm (x, c) = d
第一行输入一个整数T,表示测试的组数
第2行到T+1行,每行4个整数,分别表示a,b,c,d.数据保证a能够被b整除,d能够被c整除
1 <= T <= 2000
1 <= a, b, c, d <= 2e9
共T行,每行一个整数,如果不存在这样的x,输出0,否则,输出满足条件的x的个数
1 2 3 4 5 6 7 8 9
| >4
>41 1 96 288
>95 1 37 1776
>8481 1 999976991 1999953982
>32560 2 999992632 1999985264
|
分析
考察了唯一分解定理求lcm和gcd,打一个素数表,枚举素数,打出质因子表。详细看bilibili
CODE
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <map> #include <set> #include <deque> #include <queue> #include <vector> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout); #define PI acos(-1) #define fs first #define sc second using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll maxn = 1e6+10; double eps = 1e-8; int T; int a0,a1,b0,b1; bool vis[maxn]; int P[maxn],tail; struct node{ int a,b,c,d; }; map<int,node> mp; void initP(int N){ for(int i = 2;i<=N;i++){ if(!vis[i]) P[tail++] = i; for(int j = 0;P[j]<=N/i;j++){ vis[P[j]*i] = true; if(i%P[j] == 0) break; } } } void divP(){ int idx = 0; for(int t:{a0,a1,b0,b1}){ ++idx; for(int j = 0;j<tail && P[j]*P[j] <=t;j++){ if(t%P[j] == 0){ int cnt = 0; while(t%P[j] == 0){ cnt++; t/=P[j]; } if(idx == 1) mp[P[j]].a = cnt; if(idx == 2) mp[P[j]].b = cnt; if(idx == 3) mp[P[j]].c = cnt; if(idx == 4) mp[P[j]].d = cnt; } } if(t>1){ if(idx == 1) mp[t].a = 1; if(idx == 2) mp[t].b = 1; if(idx == 3) mp[t].c = 1; if(idx == 4) mp[t].d = 1; } } } ll fun(){ ll res = 1; for(auto p:mp){ node cur = p.second; int a = cur.a,b = cur.b,c = cur.c,d = cur.d; int cnt = 0; for(int i = 0;i<=31;i++){ if(min(i,a) == b && max(i,c) == d) cnt++; } res *= cnt; } return res; } int main(){ ios; initP(1<<16); cin>>T; while(T--){ cin>>a0>>a1>>b0>>b1; mp.clear(); divP(); cout<<fun()<<endl; } return 0; }
|