题解

37 条题解

  • 0
    @ 2015-08-19 16:38:32

    const long long Mod=10007;
    cin>>a>>b>>k>>n>>m;
    c[0]=1;
    for (int i=1;i<=k;++i) {
    c[i]=c[i-1]*(k-i+1)/i;
    }
    c[m]%=Mod;
    cout<<(c[m]*qmod(a,k-m)*qmod(b,m))%Mod;

  • 0
    @ 2014-11-06 18:25:49

    var
    a,b,k,n,m,i,j,mu,di:longint;
    c:int64;
    q:array[2..1000] of longint;

    function min(a,b:longint):longint;
    begin
    if a<=b then exit(a)
    else exit(b);
    end;

    begin
    readln(a,b,k,n,m);
    c:=1;

    for i:=1 to min(n,k-n) do
    begin
    mu:=k-i+1;di:=i;

    for j:=2 to mu do
    while (mu<>1) and (mu mod j=0) do
    begin
    inc(q[j]);
    mu:=mu div j;
    end;

    for j:=2 to di do
    while (di<>1) and (di mod j=0) do
    begin
    dec(q[j]);
    di:=di div j;
    end;

    end;

    for i:=2 to 1000 do
    if q[i]<>0 then
    for j:=1 to q[i] do
    c:=c*i mod 10007;

    for i:=1 to n do
    c:=c*a mod 10007;

    for i:=1 to m do
    c:=c*b mod 10007;

    writeln(c);
    end.

  • 0
    @ 2014-11-06 16:16:46

    var
    a,b,k,n,m,i:longint;
    c:int64;

    begin
    readln(a,b,k,n,m);
    c:=1;

    for i:=1 to n do
    c:=(c*(k-i+1) div i) mod 10007;

    for i:=1 to n do
    c:=c*a mod 10007;

    for i:=1 to m do
    c:=c*b mod 10007;

    writeln(c);
    end.

  • 0
    @ 2014-07-30 10:52:03

    C++:

    #include <cstdio>
    #define MOD 10007
    using namespace std;
    int a,b,k,n,m;
    int Pow(int x,int exp)
    {
    int ans=1,t=x%MOD;
    while (exp)
    {
    if (exp&1) (ans*=t)%=MOD;
    (t*=t)%=MOD;
    exp>>=1;
    }
    return ans;
    }
    int Get_Inv(int x)
    {
    return Pow(x,MOD-2);
    }
    //C(m,n)=m!/(m-n)!/n!
    int C(int m,int n)
    {
    int ans=1;
    for (int i=m-n+1;i<=m;i++)
    (ans*=i)%=MOD;
    for (int i=2;i<=n;i++)
    (ans*=Get_Inv(i))%=MOD;
    return ans;
    }
    int main()
    {
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    int ans=C(k,n);
    (ans*=Pow(a,n))%=MOD;
    (ans*=Pow(b,m))%=MOD;
    printf("%d\n",ans);
    getchar();getchar();
    return 0;
    }
    不用
    long long

  • 0
    @ 2014-07-26 17:22:43

    ............

  • 0
    @ 2014-07-21 17:15:46

    换成long long后终于过了

  • 0
    @ 2014-02-03 18:06:58

    这是我的代码,由于不知道怎么快速的求c(n,k)(囧呀,不过),所以我采取了一种笨方法——分解质因数,然后将c(n,k)转换为了一些质因数幂的乘积
    这是我的代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define M 10007
    const int max_k = 2001;
    const int max_pr = 400;

    short a[max_k];
    int prime_list[max_pr],r;
    int time[2][max_pr];

    int f(int a)
    {
    if (a <= 1) return 1;
    if (a >= M) return 0;
    return (a*f(a-1))%M;
    }

    void get_prmls()
    {
    int i,j;
    memset(a,1,sizeof(a));
    r = a[0] = a[1] = 0;
    for (i = 2;i < max_k;i++) {
    if (a[i]) {
    prime_list[r++] = i;
    for (j = 2;i*j < max_k;j++)
    a[i*j] = 0;
    }
    }
    }

    int power(int n,int a) // cal n^a
    {
    int static t;
    if (a == 0) return 1;
    if (n > M) return power(n%M,a);
    if (a == 1) return n;
    if (a&1) {
    t = power(n,a>>1);
    t = ((t*t)%M*n)%M;
    return t;
    } else {
    t = power(n,a>>1);
    t = (t*t)%M;
    return t;
    }
    }

    void factor(int a,int *time)
    {
    int static d;
    for (d = 0;d < r;d++) {
    while (a%prime_list[d] == 0) {
    a /= prime_list[d];
    *time = *time+1;
    }
    time++;
    }
    }

    int c(int n,int r)
    {
    int i,ans;
    memset(time,0,sizeof(time));
    get_prmls();
    for (i = n;i >= n-r+1;i--)
    factor(i,time[0]);
    for (i = 2;i <= r;i++)
    factor(i,time[1]);
    for (i = 0,ans = 1;i < max_pr;i++)
    ans = (ans*power(prime_list[i],time[0][i]-time[1][i]))%M;
    return ans;
    }

    int main()
    {
    int n,m,k,a,b,ans;
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    ans = c(k,n);
    ans = (ans*power(a,n))%M;
    ans = (ans*power(b,m))%M;
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2013-10-02 12:13:33

    朴素的杨辉三角可以秒,10行代码,注意是N,M不是M,N,第一次看错竟然还有60分= =

  • 0
    @ 2013-09-27 19:47:24

    这道题有三种解法:
    1.用递推式c(n,m)=c(n-1,m)+c(n-1,m-1)求解O(n log n)
    2.在求解直接用公式,时对乘数分解质因数,贮存质因数的个数,对分数分解质因数,减去相应的个数。O(n log n)
    3.逆元求C(k,m),O(n)

    代码(第一种思路):
    #include <cstdio>
    #define MAXN 1001
    #define rep(i,x) for (int i=0;i<x;i++)
    #define MAX 10007
    #define inf 0x7fffffff
    int n,m,a,b,k,ans;
    int c[MAXN][MAXN];
    int C(int N,int M){
    if (c[N][M]<inf) return c[N][M];
    if (N==M||M==0) return 1;
    if (N<M) return 0;
    return c[N][M]=(C(N-1,M)+C(N-1,M-1))%MAX;
    }
    int main(){
    rep(i,MAXN)rep(j,MAXN)c[i][j]=inf;
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    ans=C(k,m);
    rep(i,n) ans*=(a%MAX),ans%=MAX;
    rep(i,m) ans*=(b%MAX),ans%=MAX;
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2013-08-14 11:02:38

    var x:array[0..3000,0..3000]of longint;{(ax+by)^k--x^n*y^m}
    c,sx,sy,s,f,f1,f2,a,b,k,n,m:longint;
    begin
    {assign(input,'factor.in');
    reset(input);
    assign(output,'factor.out');
    rewrite(output);}
    read(a,b,k,n,m);
    a:=a mod 10007;
    b:=b mod 10007;
    sx:=1;sy:=1;
    for f:=1 to n do sx:=(sx*a) mod 10007;
    for f:=1 to m do sy:=(sy*b) mod 10007;
    s:=(sx*sy) mod 10007;//writeln(s);
    x[1,1]:=1;
    for f:=2 to k+1 do
    for f1:=1 to f do
    begin
    x[f,f1]:=x[f,f1] mod 10007;
    x[f-1,f1-1]:=x[f-1,f1-1]mod 10007; // begin
    x[f,f1]:=x[f-1,f1]+x[f-1,f1-1]mod 10007;// write(x[f,f1]);end;
    end;
    x[k+1,1+k-n]:=x[k+1,k+1-n]mod 10007;
    s:=s*x[k+1,1+k-n]mod 10007;
    write(s mod 10007);
    {close(input);
    close(output);}
    end.

  • 0
    @ 2013-08-14 11:01:50

    var x:array[0..3000,0..3000]of longint;{(ax+by)^k--x^n*y^m}
    c,sx,sy,s,f,f1,f2,a,b,k,n,m:longint;
    begin
    assign(input,'factor.in');
    reset(input);
    assign(output,'factor.out');
    rewrite(output);
    read(a,b,k,n,m);
    a:=a mod 10007;
    b:=b mod 10007;
    sx:=1;sy:=1;
    for f:=1 to n do sx:=(sx*a) mod 10007;
    for f:=1 to m do sy:=(sy*b) mod 10007;
    s:=(sx*sy) mod 10007;//writeln(s);
    x[1,1]:=1;
    for f:=2 to k+1 do
    for f1:=1 to f do
    begin
    x[f,f1]:=x[f,f1] mod 10007;
    x[f-1,f1-1]:=x[f-1,f1-1]mod 10007; // begin
    x[f,f1]:=x[f-1,f1]+x[f-1,f1-1]mod 10007;// write(x[f,f1]);end;
    end;
    x[k+1,1+k-n]:=x[k+1,k+1-n]mod 10007;
    s:=s*x[k+1,1+k-n]mod 10007;
    write(s mod 10007);
    close(input);
    close(output);
    end.

  • 0
    @ 2012-11-18 19:56:08

    快速幂救世界

    c++:

    #include

    using namespace std;

    long p=10007;

    long long result;

    long long fast (long x,long n)

    {

    result = 1;

    long y=x;

    while (n>0)

    {

    if (n%2==1) result=result*y %p;

    y=y * y % p;

    n = n /2;

    }

    return result;



    int main() {

    long a,b,n,m,k;

    cin>>a>>b>>k>>n>>m;

    long long tmp= fast(a,n);;

    long long tmp2=fast(b,m);

    long long tmp3=1;

    long i;

    for (i=1 ; i

  • 0
    @ 2012-10-28 13:17:02

    数组要int64 不然会挂 悲剧*2

  • 0
    @ 2012-10-27 12:03:19

    编译通过...

    ├ 测试数据 01:答案正确... (0ms, 5320KB)

    ├ 测试数据 02:答案正确... (0ms, 5320KB)

    ├ 测试数据 03:答案正确... (0ms, 5320KB)

    ├ 测试数据 04:答案正确... (0ms, 5320KB)

    ├ 测试数据 05:答案正确... (0ms, 5320KB)

    ├ 测试数据 06:答案正确... (0ms, 5320KB)

    ├ 测试数据 07:答案正确... (0ms, 5320KB)

    ├ 测试数据 08:答案正确... (0ms, 5320KB)

    ├ 测试数据 09:答案正确... (0ms, 5320KB)

    ├ 测试数据 10:答案正确... (0ms, 5320KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 0ms / 5320KB

    组合可以秒杀

    就是IGNORE说的酷似DP方程的组合性质

  • 0
    @ 2012-10-18 19:14:52

    类似杨辉

    代码 十行

    f[1,0]:=a;f[0,1]:=b;

    for i:=1 to k do

    begin

    f:=(f*a)mod 10007;

    f[0,i+1]:=(f[0,i]*b)mod 10007;

    for j:=1 to i do

    f[j,i-j+1]:=(f[j,i-j]*b+f[j-1,i-j+1]*a)mod 10007;

    end;

  • 0
    @ 2012-10-18 10:36:31

    方法同楼上,用递归不过是记忆化搜索

  • 0
    @ 2012-10-16 15:38:34

    去年做这题时根本没学过组合数……还想到了杨辉三角……

    现在我们知道组合数有个十分优美的性质,酷似DP方程:

    C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m){2

信息

ID
1739
难度
6
分类
数论 点击显示
标签
递交数
3863
已通过
1096
通过率
28%
被复制
15
上传者