牛客 7.13 月赛（留 C逆元）

B-最少剩几个？_牛客小白月赛98 (nowcoder.com)

思路

奇数+偶数 = 奇数；奇数*偶数 = 奇数

所以在既有奇数又有偶数时，两者结合可以同时删除

先分别统计奇数，偶数个数

若偶个数大于奇个数，答案是偶个数-奇个数

若奇个数大于偶个数，奇数个数减去偶个数再对2取模

ac代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)int main()
{IOS;int n,ans;int ji=0,ou=0;cin>>n;vector<ll>a(n);for(int i=0;i<n;i++) {cin>>a[i];if(a[i] & 1) ji++;else ou++; }if(ou>ji)  ans=ou-ji;else{if((ji-ou)%2) ans=1;else ans=0;}cout<<ans<<endl;   return 0;
}

C-两个函数_牛客小白月赛98 (nowcoder.com)

（超时问题如何解决）

初始代码（超时）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)int main()
{IOS;ll q,a,x;cin>>q;for(int i=0;i<q;i++){ll ans=0;cin>>a>>x;if(x==1) ans=(a*x)%998244353;else{for(int i=1;i<x;i++){ans+=(a*(a%998244353*i)%998244353)%998244353;ans%=998244353;					}}ans%=998244353;cout<<ans<<endl;}return 0;
}

解决思路

1.  快速幂

时间复杂度是 O(log n)，相比于直接进行指数运算，大大提高了计算效率

快速幂代码

int FastPow(int a,int x,int mod)
{int ans = 1;a%=mod;while(x){if(x&1) ans=(ans*a)%mod;a= (a*a)%mod;x>>=1;}return ans;
}

2.  递推式

因为是求和过程，可以用递推式

ac代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
ll mod=998244353;int main()
{IOS;ll q,a,x;cin>>q;for(int i=0;i<q;i++){ll ans=0;cin>>a>>x;if(x==1) ans=a%mod;else {a = a*a %mod;ans=(x-1)*x/2 %mod *a %mod;}cout<<ans<<endl;}return 0;
}