一、计算系数
首先对题目多项式进行简化分析
(x+y)2=x2+2xy+y2
(x+y)3=x3+3x2y+3xy2+y2
(x+y)4=x4+4x3y+6x2y2+4xy3+y4
不难发现它们的系数组成了一个杨辉三角
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
……
进一步带入则可得
(ax+by)2=a2x2+2abxy+b2y2
(ax+by)3=a3x3+3a2bx2y+3ab2xy2+b3y3
(ax+by)4=a4x4+4a3bx3y+6a2b2x2y2+4ab3xy3+b4y4
……
于是得(ax+by)k中xnym项的系数为(杨辉三角的第(k+1)行第(m+1)或(k-n+1)个的值*(anbm))的值
下面为代码:
#include<bits/stdc++.h>
#define mod 10007
using namespace std;
long long a,b,k,n,m;
long long yh[5010][5010];
int Pow(int x,int y){//计算幂
long long r=1;
for(long long i=1;i<=y;i++){
r*=x;
if(r>=mod)r%=mod;
}
return r;
}
void dfs(int x,int y){//杨辉三角
if(y>x)dfs(x+1,1);
else{
yh[x][y]=yh[x-1][y]+yh[x-1][y-1];
if(yh[x][y]>=mod)yh[x][y]%=mod;
if(x==k+1&&y==m+1){
cout<<(yh[x][y]*Pow(a,n)*Pow(b,m))%mod;
return;
}
dfs(x,y+1);
}
}
int main(){
cin>>a>>b>>k>>n>>m;
yh[1][1]=1;
dfs(2,1);
}二、聪明的质检员
三、观光公交
这道题本人主要就是贪心思想
首先记录每个景点最后一个乘客来到出发地的时间与这个景点(从前一个景点来)最迟到达时的时间。然后分析在哪个时刻使用氮气加速才是省时最多的(贪心):当这个景点的乘客开始等待时,公交还在来的路上,即这个景点的到达时间晚于最后一个乘客来到出发地的时候，使用氮气加速器可以减少乘客等待的时间。但也许会有很多个这种时候，所以要将它们记录下来，每次加速取省时最多的，再更新再继续进行此操作直到此时氮气加速器使用完(途中注意D[i]>0)
代码如下:
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int d[1010];
int t,a,b;
int num[1010],times[1010],wait[1010],rest[1010];
int ans=0;
int main(){
cin>>n>>m>>k;
for(int i=2;i<=n;i++)
scanf("%d",&d[i]);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&t,&a,&b);
wait[a]=max(wait[a],t);
ans-=t;
num[b]++;
}
for(int i=2;i<=n;i++)
times[i]=max(wait[i-1],times[i-1])+d[i];
for(int i=1;i<=k;i++){
for(int j=n;j>=2;j--){
rest[j]=num[j];
if(wait[j]<times[j])rest[j]+=rest[j+1];
}
int maxn=-1,u=0;
for(int j=2;j<=n;j++)
if(rest[j]>maxn&&d[j]>0){
maxn=rest[j];
u=j;
}
d[u]--;
for(int j=u;j<=n;j++)
times[j]=max(wait[j-1],times[j-1])+d[j];
}
for(int i=2;i<=n;i++)ans+=num[i]*times[i];
printf("%d",ans);
}其中有点难理解的地方：
ans:如果在后面减去t也没有问题,只是分开更简洁些
rest[]:如果在第i路段加速造福的乘客(能被减少等待时间的乘客数)
times[]:到达第i景点的时间
num[]:在第i个景点下车的乘客数
wait[]:第i个景点最后一个来到的乘客的时间