/ Vijos / 题库 / 组合数问题 /

题解

12 条题解

  • 2
    @ 2017-10-23 16:55:45 
    #include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int a[2001][2001];
long long b[2001][2001];
int t,k,m,n;
void yhsj()
{
    for(int i=0;i<=2000;i++)
    {
        a[i][i]=1;
        a[i][0]=1;
    }
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<i;j++)
        {
            a[i][j]=(a[i-1][j]+a[i-1][j-1])%k;
            if(a[i][j]==0)
            {
                b[i][j]=1;
            }
        }
    }
    return;
}
void qzh()
{
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=2000;j++)
        {
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    }
    return;
}
void work()
{
    scanf("%d%d",&n,&m);
    if(m>n)
    {
        m=n;
    }
    printf("%lld\n",b[n][m]);
    return;
}
int main()
{
    scanf("%d%d",&t,&k);
    yhsj();
    qzh();
    while(t--)
    {
        work();
    }
    return 0;
}
  • 1
    @ 2017-11-08 20:22:32 
    Var
    c: array[0..2000, 0..2000] of longint;
    a: array[0..2000, 0..2000] of longint;
    t, k, m, n, i, j: integer;

Begin
    //初始化
    read(t, k);
    for i:= 0 to 2000 do
        for j:= 0 to 2000 do
            c[i, j]:= -1;
    //构建杨辉三角形
    for i:= 0 to 2000 do
    begin
        c[i, 0]:= 1;
        c[i, i]:= 1;
    end;
    for i:= 1 to 2000 do
        for j:= 1 to (i-1) do
            c[i, j]:= (c[i-1, j-1] + c[i-1, j]) mod k; //避免超范围
    //处理杨辉三角形
    for i:= 0 to 2000 do
        for j:= 0 to 2000 do
            if c[i, j] = 0 then
                c[i, j]:= 1 //如果整除则为1
            else
                c[i, j]:= 0;
    //前缀和
    for j:= 0 to 2000 do
        a[0, j]:= 0;
    for i:= 1 to 2000 do
        for j:= 0 to 2000 do
            a[i, j]:= a[i-1, j] + c[i, j];
    for j:= 1 to 2000 do
        for i:= 0 to 2000 do
            a[i, j]:= a[i, j] + a[i, j-1];
    //IO
    for i:= 1 to t do
    begin
        read(n, m);
        writeln(a[n, m]);
    end;
End.
  • 1
    @ 2017-09-28 23:10:34

    用组合数递推式预处理就OK。

    #include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std; 
template <class _T> inline void read(_T &_x) {
    int _t; bool _flag=false;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
    if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
    if(_flag) _x=-_x;
}
const int maxn=2005;
int n,m,t,k;
LL C[maxn][maxn],s[maxn][maxn],ans;
bool f[maxn][maxn];
inline void get(){
    C[1][0]=C[1][1]=1;
    for(register int i=2;i<=2000;++i){
        C[i][0]=1;
        for(register int j=1;j<=i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
            if(C[i][j]%k==0)f[i][j]=1;
            s[i][j]=s[i][j-1]+f[i][j];
        }
    }
}
int main(){
    read(t),read(k);
    get();
    while(t--){
        read(n),read(m);
        ans=0;
        for(int i=1;i<=n;i++){
            ans+=s[i][min(i,m)]; 
        }
        printf("%lld\n",ans);
    } 
    
    return 0;
}
  • 1
    @ 2017-02-20 21:21:26

    通过暴力得，构造杨辉三角后直接取模即可。
    代码如下：

    #include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int T,k,n,m;
int f[2005][2005],ans[2005][2005];

int now;char ch;
inline int get_num()
{
    now=0;ch=getchar();
    while(ch<'0'|| ch>'9')ch=getchar();
    while('0'<=ch && ch<='9'){now=(now<<1)+(now<<3)+ch-'0';ch=getchar();}
    return now;
}

void init()
{
    f[1][1]=1;
    for(int i=2;i<=2001;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]=(f[i-1][j]+f[i-1][j-1])%k;
            if(j!=i)ans[i][j]=ans[i][j-1]+ans[i-1][j]-ans[i-1][j-1];
            else ans[i][j]=ans[i][j-1];
            if(f[i][j]==0)ans[i][j]++;
        }
    }
}

int main()
{
    T=get_num();k=get_num();
    init();
    for(int t=1;t<=T;t++)
    {
        n=get_num();
        m=get_num();
        if(m>n)m=n;
        printf("%d\n",ans[n+1][m+1]);
    }
    return 0;
}
  • 0
    @ 2017-11-03 21:11:37 
    #include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int t,key;
int n[10000+1];
int m[10000+1];
int c[2000+1][2000+1];
int f[2000+1][2000+1];

int main()
{
    while (~scanf("%d%d",&t,&key))
    {
        int size_c=0;
        for (int i=1;i<=t;i++)
        {
            scanf("%d%d",&n[i],&m[i]);
            m[i]=min(m[i],n[i]);
            size_c=max(size_c,n[i]);
        }
        memset(c,0,sizeof(c));
        for (int i=0;i<=size_c;i++)
        {
            c[i][0]=c[i][i]=1;
            for (int j=1;j<i;j++)
                c[i][j]=(c[i-1][j-1]+c[i-1][j])%key;
        }
        memset(f,0,sizeof(f));
        for (int i=0;i<=size_c;i++)
            for (int j=0;j<=i;j++)
                f[i][j]=((c[i][j]==0)?1:0);
        for (int i=1;i<=size_c;i++)
            for (int j=1;j<=i;j++)
                f[i][j]+=f[i-1][j];
        for (int i=1;i<=size_c;i++)
            for (int j=1;j<=i;j++)
                f[i][j]+=f[i][j-1];
        for (int i=1;i<=t;i++)
            printf("%d\n",f[n[i]][m[i]]);
    }
}
  • 0
    @ 2017-11-02 17:39:19

    谁能帮我看看这个为啥只有75分
    2、6、12、14、16的评测点错了，其他都对

    #include<stdio.h>
#include<string.h>
int k,m=0,n=1,a[2001][2001],f[2001][2001],cnt=0,t;
int getf(int,int);
int main(){
    scanf("%d %d",&t,&k);
    while(t){
        int a,b,c;
        scanf("%d",&a);
        scanf("%d",&b);
        if(a<0) a=0;
        if(b<0) b=0;
        if(b>a) b=a;
        c=getf(a,b);
        printf("%d\n",c);
        t--;
    }
    return 0;
}
int getf(int tn,int tm){
    if(tn>n || (tn==n && tm>m)){
        while(n<=tn){
            if(m==0||m==n) a[n][m]=1;
            else a[n][m]=a[n-1][m]+a[n-1][m-1];
            a[n][m]%=k;
            if(a[n][m]==0) cnt++;
            f[n][m]=cnt+(m==n?f[n-1][m-1]:f[n-1][m]);
            m++;
            if(m>n){
                n++;m=0;cnt=0;
            }
            if(n==tn&&m>tm)break;
        }
    }
    return(f[tn][tm]);
}
  • 0
    @ 2017-05-04 15:10:47

    杨辉三角然后前缀和即可
    一维或者二维都可以
    然而考试的时候想到了前缀和数组开小了
    真是有意思

    #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;

char rd;    int pn;
template<typename Type>
inline void read(Type& v)
{
    pn=1;
    while((rd=getchar())<'0'||rd>'9')
        if(rd=='-')
            pn=-1;
    v=rd-'0';
    while((rd=getchar())>='0'&&rd<='9')
        v=v*10+rd-'0';
    v*=pn;
}
template<typename Type>
inline void out(Type v,bool c=1)
{
    if(v==0)
        putchar(48);
    else  
    {
        if(v<0)
        {
            putchar('-');
            v=-v;
        }
        int len=0,dg[20];  
        while(v>0)
        {
            dg[++len]=v%10;
            v/=10;
        }  
        for(int i=len;i>=1;i--)
            putchar(dg[i]+48);  
    }
    if(c)
        putchar('\n');
    else
        putchar(' ');
}

const int MAXN=2005;
int c[MAXN][MAXN];
int f[MAXN][MAXN];
int n,m,t,k;

void init()
{
    read(t);    read(k);
}

void work()
{
    for(int i=1;i<=2002;i++)
        c[i][0]=c[i][i]=1;
    for(int i=2;i<=2002;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
    for(int i=1;i<=2002;i++)
    {
        for(int j=1;j<=i;j++)
            if(!c[i][j])
                f[i][j]=f[i][j-1]+1;
            else
                f[i][j]=f[i][j-1];
    }
}

void question()
{
    int ans;
    for(int i=1;i<=t;i++)
    {
        ans=0;
        read(n);    read(m);
        for(int j=1;j<=n;j++)
            ans+=f[j][min(j,m)];
        out(ans);
    }
}

int main()
{
    init();
    work();
    question();
    return 0;
}
  • -1
    @ 2018-07-30 21:37:59

    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int t,k,n,m,f[2005][2005],c[2005][2005];
    int main(){
    scanf("%d%d",&t,&k);
    for (int i=0;i<=2000;i++) f[i][0]=f[i][i]=1;
    for (int i=1;i<=2000;i++)
    for(int j=1;j<=i;j++){
    f[i][j]=((f[i-1][j-1]%k)+(f[i-1][j]%k))%k;
    }
    for(int i=1;i<=2000;i++)
    for(int j=1;j<=2000;j++){
    c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
    if (!f[i][j]&&i>=j) c[i][j]++;
    }
    for(int i=1;i<=t;i++){
    scanf("%d%d",&n,&m);
    printf("%d\n",c[n][m]);
    }
    }

  • -1
    @ 2017-11-09 22:02:06

    #include<cstdio>
    #include<cstring>
    using namespace std;
    int m,n,k,t,san[2005][2005],ans[2005][2005];//san存杨辉三角，ans存答案
    int main()
    {
    scanf("%d %d",&t,&k);
    for (int i=0;i<=2002;i++)
    {
    int sum=0;//sum记每行第j个数之前有几个数能被k整除
    for (int j=0;j<=i;j++)
    {
    if (j==0) san[i][j]=1;
    else san[i][j]=(san[i-1][j-1]+san[i-1][j])%k;//初始化杨辉三角，先mod k避免数太大超出int范围
    if (san[i][j]==0)//当mod结果为0时说明该数能被k整除，sum加1并存入ans数组的对应位置
    {
    sum++;
    ans[i][j]=sum;
    }
    else ans[i][j]=sum;//否则sum数值不变，依旧存入ans
    }
    }

    for (int i=1;i<=t;i++)
    {
    int h=0;
    scanf("%d %d",&n,&m);
    for (int j=0;j<=n;j++)//一行一行扫
    {
    if (j<m) h+=ans[j][j];//当j小于m的时候取第j个数的答案
    else
    h+=ans[j][m];//当j大于m时j以后的数不能算进来，所以只取第j个数答案
    }

    printf("%d\n",h);
    }
    return 0;
    }

  • -1
    @ 2017-08-09 13:03:49

    构造杨辉三角的过程中对k取模
    用二维前缀和优化一下
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int n,m,t,k,a[10100],b[10100],f[3001][3001];
    int c[3001][3001];
    int maxn=-10,maxm=-10,k1,ans;

    void work2()
    {
    f[0][0]=1;
    f[1][0]=f[1][1]=1;
    for(int i=1;i<=2002;i++)
    {
    f[i][i]=1;
    f[i][0]=1;
    }
    for(int i=1;i<=2002;i++)
    for(int j=1;j<=i;j++)
    { f[i][j]=(f[i-1][j]+f[i-1][j-1])%k1;
    if(!f[i][j])
    c[i][j]=c[i][j-1]+1;
    else
    c[i][j]=c[i][j-1];
    }

    }
    int main()
    {
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    scanf("%d%d",&t,&k1);
    memset(f,0,sizeof(f));
    memset(c,0,sizeof(c));
    work2();
    for(int i=1;i<=t;i++)
    {ans=0;
    scanf("%d%d",&n,&m);
    for(int j=1;j<=n;j++)
    ans+=c[j][min(j,m)];
    printf("%d\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
    }

  • -1
    @ 2017-03-24 16:14:30 
    #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int L=2002;
int a[L][L],b[L][L],t,k,n,m;

inline int rd()
{
    int ret=0;char c=getchar();
    while (c>'9'||c<'0') c=getchar();
    while (c>='0'&&c<='9') ret=ret*10+c-'0',c=getchar();
    return ret;
}
int main()
{
    t=rd(),k=rd();
    memset(b,0,sizeof(b));
    for (int s=0;s<L;s++) a[s][0]=a[s][s]=1;
    for (int s=1;s<L;s++)
        for (int t=1;t<s;t++)
            a[s][t]=(a[s-1][t]+a[s-1][t-1])%k;//杨辉三角递推Cij并取模
    for (int s=1;s<L;s++)
        for (int t=1;t<L;t++)
            if (!a[s][t]&&s>=t)
                                b[s][t]=1;//统计整除数
    for (int s=1;s<L;s++)
        for (int t=1;t<L;t++)
            b[s][t]+=b[s][t-1];
    for (int s=1;s<L;s++)
        for (int t=1;t<L;t++)
            b[s][t]+=b[s-1][t];      //二维前缀和
    while (t--)
    {
        n=rd(),m=rd();
        printf("%d\n",b[n][m]);
    }
}
  • -3
    @ 2017-02-15 10:48:39

    编译成功

    测试数据 #0: Accepted, time = 109 ms, mem = 32512 KiB, score = 5
    测试数据 #1: Accepted, time = 187 ms, mem = 32516 KiB, score = 5
    测试数据 #2: Accepted, time = 109 ms, mem = 32512 KiB, score = 5
    测试数据 #3: Accepted, time = 93 ms, mem = 32516 KiB, score = 5
    测试数据 #4: Accepted, time = 78 ms, mem = 32512 KiB, score = 5
    测试数据 #5: Accepted, time = 125 ms, mem = 32516 KiB, score = 5
    测试数据 #6: Accepted, time = 93 ms, mem = 32512 KiB, score = 5
    测试数据 #7: Accepted, time = 109 ms, mem = 32512 KiB, score = 5
    测试数据 #8: Accepted, time = 109 ms, mem = 32512 KiB, score = 5
    测试数据 #9: Accepted, time = 156 ms, mem = 32516 KiB, score = 5
    测试数据 #10: Accepted, time = 125 ms, mem = 32512 KiB, score = 5
    测试数据 #11: Accepted, time = 125 ms, mem = 32516 KiB, score = 5
    测试数据 #12: Accepted, time = 78 ms, mem = 32512 KiB, score = 5
    测试数据 #13: Accepted, time = 93 ms, mem = 32516 KiB, score = 5
    测试数据 #14: Accepted, time = 78 ms, mem = 32516 KiB, score = 5
    测试数据 #15: Accepted, time = 125 ms, mem = 32516 KiB, score = 5
    测试数据 #16: Accepted, time = 78 ms, mem = 32516 KiB, score = 5
    测试数据 #17: Accepted, time = 109 ms, mem = 32512 KiB, score = 5
    测试数据 #18: Accepted, time = 78 ms, mem = 32512 KiB, score = 5
    测试数据 #19: Accepted, time = 78 ms, mem = 32516 KiB, score = 5
    Accepted, time = 2135 ms, mem = 32516 KiB, score = 100

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    #define LL long long

    int t,n,m,k,ANS;
    int prime[9]={0,2,3,5,7,11,13,17,19};
    int p[2005][20],s[2005][20],a[20],b[20],c[20],d[20],ans[2005][2005],Ans[2005][2005];

    void calc(int x)
    {
    int now=x;if (now==1) return;
    for (int i=1;i<=8;++i)
    if (now%prime[i]==0)
    {
    while (now%prime[i]==0)
    p[x][i]++,now/=prime[i];
    if (now==1) break;
    }
    }
    void sum(int x)
    {
    for (int i=1;i<=8;++i)
    s[x][i]=s[x-1][i]+p[x][i];
    }
    int main()
    {
    scanf("%d%d",&t,&k);
    for (int i=1;i<=2000;++i)
    calc(i);
    for (int i=1;i<=2000;++i) sum(i);
    for (n=0;n<=2000;++n)
    {
    bool flag=true;
    for (int i=1;i<=8;++i) a[i]=s[n][i],b[i]=s[n][i],c[i]=0,d[i]=a[i]-b[i]-c[i]-p[k][i];
    for (int i=1;i<=8;++i)
    {
    if (d[i]<0) {flag=false;break;}
    }
    if (flag) ans[n][0]++;
    for (m=1;m<=n;++m)
    {
    bool flag=true;
    for (int i=1;i<=8;++i) b[i]-=p[n-m+1][i],c[i]+=p[m][i],d[i]=a[i]-b[i]-c[i]-p[k][i];
    for (int i=1;i<=8;++i)
    {
    if (d[i]<0) {flag=false;break;}
    }
    if (flag) ans[n][m]++;
    }
    }
    for (int i=0;i<=2000;++i) Ans[i][0]=ans[i][0],Ans[0][i]=ans[0][i];
    for (int i=1;i<=2000;++i)
    for (int j=1;j<=2000;++j) Ans[i][j]=Ans[i-1][j]+Ans[i][j-1]-Ans[i-1][j-1]+ans[i][j];
    while (t--)
    {
    scanf("%d%d",&n,&m);
    printf("%d\n",Ans[n][m]);
    }
    return 0;
    }

  • 1

组合数问题

信息

ID
2006
难度
6
分类
(无)
标签
递交数
1816
已通过
501
通过率
28%
被复制
8
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1