题解

12 条题解

  • 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-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-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
分类
(无)
标签
递交数
1714
已通过
463
通过率
27%
被复制
1
上传者