WD与循环
为什么大家都是先算\(n\)个数的和等于\(m\)的情况再求前缀和?
既然已经想到了插板法,为什么不直接对\(n\)个数的和\(\le m\)的情况做呢?
基本套路没有变:考虑对于\(n\)个非负整数,先变成\(n\)个正整数,求和\(\le m + n\)的情况。下面是不同的地方:在\(m + n\)个小球之间插入\(n\)块板子,具体地说,在每个球的右边可以插入一块板子,对于从左往右数第\(i\)块板子,它到第\(i - 1\)块板子或者左端点之间的小球数就是第\(i\)个数,对于最右边的一块板子,它左边的板子数即没有被分到任何一个数中的小球个数一定\(\ge 0\),这正好对应了我们\(\le m + n\)的条件。得到式子\(\binom {n + m} {n}\),lucas定理即可。
yyb是我们的红太阳,%yyb有益身心健康
//written by newbiechd
#include <cstdio>
#include <cctype>
#define R register
#define I inline
#define B 1000000
#define L long long
using namespace std;
const int yyb = 19491001;
char buf[B], *p1, *p2;
I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }
I L rd() {
L f = 0;
R char c = gc();
while (c < 48 || c > 57)
c = gc();
while (c > 47 && c < 58)
f = f * 10 + (c ^ 48), c = gc();
return f;
}
L a[yyb];
I L pow(L x, L y) {
L r = 1;
for (x %= yyb; y; y >>= 1, x = x * x % yyb)
if (y & 1)
r = r * x % yyb;
return r;
}
I L com(L n, L m) {
if (m > n)
return 0;
return a[n] * pow(a[m], yyb - 2) % yyb * pow(a[n - m], yyb - 2) % yyb;
}
L lucas(L n, L m) {
if (!m)
return 1;
return com(n % yyb, m % yyb) * lucas(n / yyb, m / yyb) % yyb;
}
int main() {
R int T = rd(), i;
L n, m;
a[0] = 1;
for (i = 1; i < yyb; ++i)
a[i] = a[i - 1] * i % yyb;
for (i = 1; i <= T; ++i)
n = rd(), m = rd(), printf("%lld\n", lucas(n + m, n));
return 0;
}