牛客挑战赛73

好难QWQ

img

A

求和可以直接用求和公式计算

由于gcd(a,b)=gcd(b,a%b)

因此可以每次都对阶乘取模

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int gcd(int a,int b)
{
    return  b?gcd(b,a%b):a;
}
signed main()
//gcd(a,b)=gcd(b,a%b)
{
int n;
cin>>n;
ll a=n*(n+1)/2;
ll ans=1;
rep(i,1,n)
{
ans=ans*i%a;
}
ans =gcd(ans,a);
cout<<ans;
return 0;
}

B

使用两个队列，一个存取上一次遍历的结果，一个存取本次遍历的结果，注意上一个结果需要进行清空，先遍历上一次的右和下，然后记录起来，再把相同的塞进下一个队列，期间记录答案即可。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const int N=2050;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
string s[N];
char ans[N+10];
int n,m;
struct node
{
int x,y;
};
bool vis[N][N];
vector<node>q[2];

signed main()
{
ios;
cin>>n>>m;
rep(i,1,n)
{
    cin>>s[i];
    s[i]=" "+s[i];
}
int c=0;
int w=1;
q[c].push_back(node{1,1});
vis[1][1]=1;
ans[w]=s[1][1];
rep(i,1,n+m-2)
{
    c^=1;
    q[c].clear();
    //转移到下一层
    char o='z';
    for(node u:q[c^1])
    {
        int x=u.x;
        int y=u.y;
        if(x<n)
        {
o=min(o,s[x+1][y]);
        }
        if(y<m)
        {
            o=min(o,s[x][y+1]);
        }
    }
        ans[++w]=o;
        for(node u:q[c^1])
        {
            int x=u.x;
            int y=u.y;
            if(x<n&&s[x+1][y]==o&&!vis[x+1][y])
            {
                q[c].push_back(node{x+1,y});
                vis[x+1][y]=1;
            }
            if(y<m&&s[x][y+1]==o&&!vis[x][y+1])
            {
                q[c].push_back(node{x,y+1});
                vis[x][y+1]=1;
            }
        }
    
}
for(int i=1;i<=w;i++)
{
    cout<<ans[i];
}

    return 0;
}

C

求和是可以直接用公式的

image-20240411092650580

下面公式详见：牛客挑战赛73题解（A~C）-CSDN博客

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const int N=2050;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a,b,x;
int qmi(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void Totoro()
{
cin>>a>>b>>x;
	cout<<(a*x%mod+b)%mod<<' ';
    cout<<(a*x%mod*(x+1)%mod*qmi(2,mod-2)%mod+b*x%mod)%mod<<' ';
    cout<<(((x*(x+1)%mod*qmi(4,mod-2)%mod+x*(x+1)%mod*(2*x+1)%mod*qmi(12,mod-2)%mod)%mod*a%mod)+b*x%mod*(x+1)%mod*qmi(2,mod-2)%mod)%mod<<' ';
    cout<<(qmi(x*(x+1)%mod,2)*qmi(24,mod-2)%mod*a%mod+x*(x+1)%mod*(2*x+1)%mod*qmi(12,mod-2)%mod*a%mod+x*(x+1)%mod*qmi(6,mod-2)%mod*a%mod+x*(x+1)%mod*qmi(4,mod-2)%mod*b%mod+x*(x+1)%mod*(2*x+1)%mod*qmi(12,mod-2)%mod*b%mod)%mod;    
}
signed main()
{
    ios;
    int T=1;
	cin>>T;
	while(T--)
	{
		Totoro();
	}
}