就做了两个数学题
链接:https://www.nowcoder.com/acm/contest/73/A
来源:牛客网
白兔的分身术
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
白兔学会了分身术。
一开始有一只白兔,接下来会进行k轮操作,每一轮中每一只白兔都会变成p只白兔。
要求k轮后白兔的总数恰好为n。
要求找到两个正整数p,k,最大化p+k
输入描述:
输入一个正整数n(2<=n<=1018)
输出描述:
输出一个整数,p+k的最大值
示例1
输入
2
输出
3
说明
p=2,k=1
我们都知道指数递增最快,这个还要求恰好,所以就一次直接到好了 n+1
#include<bits/stdc++.h> using namespace std; int main() { long long n; cin>>n; cout<<n+1; return 0; }
链接:https://www.nowcoder.com/acm/contest/73/B
来源:牛客网
白兔的式子
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
已知f[1][1]=1,f[i][j]=a*f[i-1][j]+b*f[i-1][j-1](i>=2,1<=j<=i)。
对于其他情况f[i][j]=0
有T组询问,每次给出a,b,n,m,求f[n][m] mod (998244353)
输入描述:
第一行为一个整数T,表示询问个数。
接下来一共T行,每行四个整数a,b,n,m。
输出描述:
一共T行,每行一个整数,表示f[n][m] mod (998244353)
示例1
输入
2 2 3 3 3 3 1 4 1
输出
9 27
备注:
T<=100000
1<=m<=n<=100000
0<=a,b<=109
B这个递推式一看就是组合数的递推式,也就是杨辉三角
然后进一步找其递推式,在左边就会乘上a,右边第几个就会是b^(m-1),需要乘多少次a不难发现是n-m次
C(m-1,n-1)*a^(n-m)*b^(m-1)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MD=998244353LL,N=1e5+5; ll la(ll a,ll b) { a%=MD; ll ans=1;while(b>0) { if(b&1)ans=ans*a%MD; b>>=1; a=a*a%MD; } return ans; } ll f[N],v[N]; ll C(ll n,ll m) { if(m<0||m>n) return 0; return 1LL*f[n]*v[m]%MD*v[n-m]%MD; } int main() { f[0]=1; for (ll i=1; i<N; i++) f[i]=1LL*f[i-1]*i%MD; v[N-1]=la(f[N-1],MD-2); for (ll i=N-2; i>=0; i--) v[i]=v[i+1]*(i+1LL)%MD; ll T; scanf("%lld",&T); while (T--) { ll a,b,n,m; scanf("%lld%lld%lld%lld",&a,&b,&n,&m); printf("%lld ",C(n-1,m-1)*la(a,n-m)%MD*la(b,m-1)%MD); } return 0; }