Problem A 简单计数

https://ac.nowcoder.com/acm/contest/879/A

题意:

题解:矩阵快速幂+构造矩阵

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100+10;
const int M=100000+10;
const int MOD=998244353;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int cnt,flag,temp,sum;
int a[N];

struct Matrix{
	int n;
	Matrix(int nn = 1):n(nn){ memset(a,0,sizeof(a));};
	long long a[N][N];
	void print(){
        for(int i = 0;i <= n; ++i)
            for(int j= 0;j <= n; ++j)
                printf("%lld%c",a[i][j]," \n"[j==n]);
    }
    Matrix operator*(const Matrix &b)const{
        Matrix c(n);
        for(int i = 0;i <= n; ++i){
            for(int j = 0;j <= n; ++j){
                for(int k = 0;k <= n; ++k){
                    c.a[i][j] += a[i][k] * b.a[k][j];
                    c.a[i][j] %= MOD;
                }
            }
        }
        //c.print();
        return c;
    }
};
Matrix ans,fac;
ll POW(ll a,ll b,ll c){
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return res;
}

void MatrixPOW(ll k){
    while(k){
        if(k&1)ans=ans*fac;
        fac=fac*fac;
        k>>=1;
    }
}
void init(){

    ans.n =  fac.n  = 2;
    ans.a[0][0] = 1;
    ans.a[1][1]=1;
    ans.a[0][1] = 0;
    fac.a[0][0] = 0;
    fac.a[0][1] = n-1;
    fac.a[1][0] = 1;
    fac.a[1][1] = n-2;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%lld%lld",&n,&k);
    init();
    //ans.print();
    //fac.print();
    MatrixPOW(k);
    //ans.print();
    cout<<ans.a[0][0]<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem B 投硬币

https://ac.nowcoder.com/acm/contest/879/B

题意:

题解:乘法逆元+概率

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const ll MOD=998244353;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
ll a[N];
char str;
struct node{};
ll POW(ll a,ll b,ll c){
    //cout<<a<<" "<<b<<" "<<c<<endl;
    if(a==0)
        return 1;
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    a[1]=1;
    a[0]=1;
    for(int i=2;i<N;i++)
        a[i]=(a[i-1]*i)%MOD;
    scanf("%lld%lld%lld",&n,&k,&p);
    ans=0;
    for(int i=k;i<=n;i++){
        ans=(ans+((a[n]*POW(p,i,MOD)%MOD)*POW((1-p+MOD)%MOD,n-i,MOD)%MOD)*POW(a[i]*a[n-i]%MOD,MOD-2,MOD)%MOD)%MOD;
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem C 植树造林

https://ac.nowcoder.com/acm/contest/879/C

题意:

题解:数学+思维

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    cout<<(n%2?1:2)<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem D 签到题I

https://ac.nowcoder.com/acm/contest/879/D

题意:

题解:排序

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    cout<<a[k]<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem E 等比数列三角形

https://ac.nowcoder.com/acm/contest/879/E

题意:

题解:

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    ans = 0;
    double e = (1 + sqrt(5)) / 2;
    for(int i = 1; i * i <= n; i++)
        for(int j = i; j <= e * i; j++)
            if(__gcd(i, j) == 1) ans = (ans + n / j / j)%MOD;
    cout << ans << endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

 C++版本二

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define endl '\n'
const int mod=1e9+7;
LL n;
double e=(1.0+sqrt(5.0))/2;
LL b[5000];
int main()
{
    while(cin>>n){
    LL ans=n;
    int sqr=sqrt(n);
    for(int i=2;i<=sqr;i++){
        b[i]=i-(int)(i/e)-1;
    }
    for(int i=2;i<=sqr;i++){
        for(int j=i*2;j<=sqr;j+=i){
            b[j]-=b[i];
        }
        ans=(ans+(n/(i*i))*b[i])%mod;
    }
    cout<<ans<<endl;
    }
 
    return 0;
}

Problem F 乐色王传奇

https://ac.nowcoder.com/acm/contest/879/F

题意:

题解:

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=2500+10;
const int M=10000000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp=1,sum;
int a[N][N],inv[N];
int vis[N];
char str;
struct node{
    int v,id;
    node(){};
    node(int _v,int _id){
        v=_v,id=_id;
    }
    bool operator <(const node &S)const{
        return v<S.v;
    }
}e[M];
ll POW(ll a,ll b,ll c){
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]),e[(i-1)*n+j]=node(a[i][j],i);
    sort(e+1,e+n*n+1);
    int zercnt=n;inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
    for(int i=1;i<=n*n;i++){
        if(!vis[e[i].id]++)
            zercnt--;
        if(vis[e[i].id]>1)
            temp=1LL*temp*inv[vis[e[i].id]-1]%MOD*vis[e[i].id]%MOD;
        if(!zercnt)
            ans=(ans+1LL*temp*inv[vis[e[i].id]]%MOD*e[i].v)%MOD;
    }
    printf("%lld\n",1LL*ans*POW(POW(n,n,MOD),MOD-2,MOD)%MOD);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem G many sum

https://ac.nowcoder.com/acm/contest/879/G

题意:

题解:朴素

C++版本一

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int a1[maxn];
long long b[maxn];
int main()
{
    int n,a,m;
    cin >> n >> a >> m;
    a1[1] = a;
    for(int i = 2; i <= n;i++){
        a1[i] = (a1[i - 1] + 7 * i) % m;
    }
    for(int i = 1; i <= n;i++){
        for(int j = i; j <= n; j+=i){
            b[j]=b[j]+a1[i];
        }
    }
    long long  ans = 0;
    for(int i = 1; i <= n;i++){
        ans^=b[i];
    }
    cout << ans << endl;
}

Problem H 图上计数

https://ac.nowcoder.com/acm/contest/879/H

题意:

题解:

C++版本一

 

Problem I 有毒的玻璃球

https://ac.nowcoder.com/acm/contest/879/I

题意:

题解:积性函数+快速幂

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=10000000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
ll D[M];
int pre[M];
bool prime[M];
ll POW(ll a,ll b,ll c){
    //cout<<a<<" "<<b<<" "<<c<<endl;
    if(a==0)
        return 1;
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&k);
    D[1]=1;
    prime[0]=prime[1]=1;
    for(int i=2;i<M;i++){
        if(!prime[i]){
            D[i]=POW(i,k,MOD);
            pre[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*pre[j]<M;j++){
            prime[i*pre[j]]=1;
            D[i*pre[j]]=(D[i]*D[pre[j]])%MOD;
            if(i%pre[j]==0){
                break;
            }

        }
        //cout<<i<<" "<<D[i]<<endl;
    }
    for(int i=1;i<=n;i++){
        ans=(ans+(n/i)*D[i]%MOD)%MOD;
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem J J.I

https://ac.nowcoder.com/acm/contest/879/J

题意:

题解:

C++版本一