牛客小白月赛14
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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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 DEBUGprintf("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++版本一
?
?
總結
