前两天打了第二场积分赛，难度明显比上次高，感觉更考验思维了，收集了一些我认为有价值的题目，因为太懒了，不想自己写思路题解了，搬来了别人的代码和题解，以后争取养成保存代码的习惯🐷
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;
}
|
wechat
alipay