# 12 条题解

• @ 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;
}

• @ 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
//初始化
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
writeln(a[n, m]);
end;
End.

• @ 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(){
get();
while(t--){
ans=0;
for(int i=1;i<=n;i++){
ans+=s[i][min(i,m)];
}
printf("%lld\n",ans);
}

return 0;
}

• @ 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;
}

• @ 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]]);
}
}

• @ 2017-11-03 21:11:56

很H2O的題

• @ 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]);
}

• @ 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>
{
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()
{
}

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;
for(int j=1;j<=n;j++)
ans+=f[j][min(j,m)];
out(ans);
}
}

int main()
{
init();
work();
question();
return 0;
}

• @ 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]);
}
}

• @ 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;
}

• @ 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;
}

• @ 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]);
}
}

• @ 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