NC16603. 礼物
描述
输入描述
输入的第一行包含一个整数T，表示测试组数。
每个测试用例前面都有一个空白行。
每个测试用例由包含整数N,M,K和素数P的单行组成。
输出描述
对于每个测试用例输出一个整数：表示不同的购买奥利奥的方式的数量Z mod P的值。
示例1
输入:
3 0 10 2 47 2 2 4 47 5 5 10 47
输出:
10 14 6
说明:
在第一个测试样例中，我们必须购买一包2元的奥利奥，并且有10种类型。C++14(g++5.4) 解法, 执行用时: 460ms, 内存消耗: 480K, 提交时间: 2018-06-15 19:07:33
#include<iostream>
#include<cstdio>
const int N=1005;
int dp[N],k,T,n,m,mod;
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%d%d%d",&n,&m,&k,&mod);
for(int i=1;i<=k;i++) dp[i]=0;
dp[0]=1;
for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) dp[j]+=dp[j-1],dp[j]%=mod;
for(int i=1;i<=m;i++) for(int j=2;j<=k;j++) dp[j]+=dp[j-2],dp[j]%=mod;
printf("%d\n",dp[k]);
}
return 0;
}
Python(2.7.3) 解法, 执行用时: 1411ms, 内存消耗: 5724K, 提交时间: 2018-06-16 18:17:44
a=1
b=[1]
for i in range (1,2000):
a*=i
b.append(a)
def f(n,m,p):
k=b[n]/(b[m]*b[n-m])
return k%p
t=int(raw_input())
while t>0:
t=t-1
ans=0
raw_input()
n,m,k,p = map(int, raw_input().split())
for i in range (0,k+1):
if (k-i)%2==0:
ans+=f(n+i-1,i,p)*f(m-1+(k-i)/2,(k-i)/2,p)
ans=ans%p
print(ans)
C++(clang++ 11.0.1) 解法, 执行用时: 317ms, 内存消耗: 408K, 提交时间: 2022-11-27 15:10:17
#include<iostream>
#include<cstdio>
using namespace std;
int T,n,m,k,p,f[1001];
int main()
{
cin>>T;
while(T--)
{
cin>>n>>m>>k>>p;
for(int i=0;i<=k;i++)
f[i]=0;
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
f[j]=(f[j]+f[j-1])%p;
for(int i=1;i<=m;i++)
for(int j=1;j<=k;j++)
f[j]=(f[j]+f[j-2])%p;
cout<<f[k]<<endl;
}
}