前排
by fake_spy @ 2018-09-06 18:02:14
预处理杨辉三角,每次转移时把相加后的值对k取模;
------------
并用prefix_and记录
by fake_spy @ 2018-09-06 18:03:23
@[fake_spy](/space/show?uid=62615) dalao求解答
by 2h1c @ 2018-09-06 18:03:38
@[fake_spy](/space/show?uid=62615) 蒟蒻看不懂啊,dalao破解一下这道题
by 2h1c @ 2018-09-06 18:05:34
@[EGO_](/space/show?uid=77856)
预处理组合数时要一直对k取模,不然会爆int
```
for(int i=1;i<=2000;i++){
for(int j=1;j<=i;j++){
c[i][j]=(c[i-1][j]%k+c[i-1][j-1]%k)%k;
}
}
```
by 钱逸凡 @ 2018-09-06 19:06:02
@[钱逸凡](/space/show?uid=28088) 谢谢,我好像还忘处理0了
by Extra·G·Ordinary_ @ 2018-09-06 20:10:46
修改了一下然而50分,感觉没什么可以再改的了哇QAQ
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2002;
int zh[maxn][maxn];
int ans=0;
int n,m,k,t;
inline void write(int x)
{
int y=10,len=1;
while(y<=x) {y*=10;len++;}
while(len--){y/=10;putchar(x/y+48);x%=y;}
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void tri()
{
zh[1][0]=1;
zh[1][1]=1;
zh[0][0]=1;
for(register int i=2;i<=2000;++i)
{
zh[i][0]=1;
for(register int j=1;j<=2000;++j)
{
zh[i][j]=(zh[i-1][j-1]%k+zh[i-1][j]%k)%k;
}
}
}
int main()
{
t=read();k=read();
tri();
while(t--)
{
n=read();m=read();
for(register int i=0;i<=n;++i)
for(register int j=0;j<=min(i,m);++j)
if(zh[i][j]==0)ans++;
write(ans);
}
return 0;
}
```
by Extra·G·Ordinary_ @ 2018-09-06 22:19:07
捞一下
by Extra·G·Ordinary_ @ 2018-09-07 17:48:11
觉得没错就重构
总能AC的
by EMT__Mashiro @ 2018-09-22 11:35:22
qwq这不是动态规划么(逃)
by suwakow @ 2018-09-27 19:59:31