2999. 计算多项式的系数

10195101416-NiYuanCheng

include

using namespace std;
const int mod=10007;
int main()
{
        int t,ddt;cin>>t;
        for(ddt=0;ddt<t;ddt++){
                int a,b,k,n,m;
                cin>>a>>b>>k>>n>>m;
                long long int dp[1001][1001]={0};
                int i,j;
                dp[0][0]=1;
                for(i=1;i<1001;i++){
                        dp[i][0]=1,dp[i][1]=(i%mod);
                }
                for(i=1,j=1;i<1001,j<1001;i++,j++){
                        if(i==j) dp[i][j]=1;
                }
                for(i=2;i<1001;i++){
                        for(j=1;j<=i;j++){
                                if(i>=j) dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
                        }
                }
                long long int s=dp[k][n],c=1,d=1;
                for(i=0;i<n;i++){
                        c=(c*a)%mod;
                }
                for(i=0;i<m;i++){
                        d=(d*b)%mod;
                }
                cout<<"case #"<<ddt<<":\n";
                cout<<(((((s%mod)*d)%mod)*c)%mod)<<endl;
        }
}
我太难了

这题怎么可以不说一句python大法好

import math
for i in range(int(input())):
    a,b,k,n,m=map(int,input().split())
    print ("case #{}:\n{}".format(i,pow(a,n,10007)*pow(b,m,10007)*(math.factorial(k)//(math.factorial(n)*math.factorial(k-n)))%10007))
三七茧茧

标准姿势:

include

include

include

include

include

long long int c[1005][1005];

void init()
{
c[0][0]=0;
c[1][0]=1;
c[1][1]=1;
for(int i=2;i<1001;i++)
{
c[i][0]=1;
for(int j=0;j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%10007;
}
}

void solve()
{
int a, b, k, n, m;
scanf(“%d%d%d%d%d”,&a,&b,&k,&n,&m);
long long int s=c[k][n];
for(int cnt=0;cnt<n;cnt++)
{
s=(sa)%10007;
}
for(int cnt=0;cnt<m;cnt++)
{
s=(s
b)%10007;
}
printf(“%lld\n”,s);
}

int main()
{
int i, t;
scanf(“%d”,&t);
init();
for(i=0;i<t;i++)
{
printf(“case #%d:\n”,i);
solve();
}
return 0;
}

欢迎访问我的主页!http://godweiyang.com

300题留念
300题留念[em:04][em:04][em:04]

骨川小夫

include

using namespace std;
typedef long long ll;
const int mo=10007;
ll dp[1010][1010];
int ans;
int main() {
int t;
cin>>t;
ans=0;
while(t–){
ll a,b,k,n,m;
cin>>a>>b>>k>>n>>m;
a=a%mo;
b=b%mo;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i+j==0) dp[i][j]=1;
else if(i==0) dp[i][j]=bdp[i][j-1]%mo;
else if(j==0) dp[i][j]=a
dp[i-1][j]%mo;
else dp[i][j]=(adp[i-1][j]+bdp[i][j-1])%mo;
}
}
cout<<”case #”<<ans++<<”:”<<endl;
cout<<dp[n][m]<<endl;
}
return 0;
}

Saitama

打扰了,原来是因为我把n和m输入反了

Li Dao

这题懒得烦了,直接上抄了个求组合数取模的模板

include

using namespace std;
typedef long long LL;
const int MOD=10007;
int T;

LL exp_mod(LL a, LL b, LL p) {
LL res = 1;
while(b != 0) {
if(b&1) res = (res * a) % p;
a = (a*a) % p;
b >>= 1;
}
return res;
}

LL Comb(LL a, LL b, LL p) {
if(a < b) return 0;
if(a == b) return 1;
if(b > a - b) b = a - b;

LL ans = 1, ca = 1, cb = 1;
for(LL i = 0; i < b; ++i) {
    ca = (ca * (a - i))%p;
    cb = (cb * (b - i))%p;
}
ans = (ca*exp_mod(cb, p - 2, p)) % p;
return ans;

}

LL Lucas(int n, int m, int p) {
LL ans = 1;

 while(n&&m&&ans) {
    ans = (ans*Comb(n%p, m%p, p)) % p;
    n /= p;
    m /= p;
 }
 return ans;

}

LL Pow(LL a,LL b)
{
LL ret=1;
for(LL i=1;i<=b;i++) ret=(reta)%MOD;
return ret;
}
void solve()
{
LL a,b,k,n,m;
cin>>a>>b>>k>>n>>m;
if(n+m!=k) cout<<0<<endl;
else
{
LL ans=Pow(a,n);
ans=(ans
Pow(b,m))%MOD;
ans=(ans*Lucas(k,n,MOD))%MOD;
cout<<ans<<endl;
}
return;
}

int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

另一种方法,注意算组合数的时候乘和除的顺序,让偶数除偶数,也可以做

51174500037

Lucas定理

一剑无痕雪满山

300题留念
[em:12][em:12][em:12]队形。。
楼上眼熟2333

你当前正在回复 博客/题目
存在问题!