## 【日常小测】计数

### 一句话题意

$n_1,n_2,n_3,n_4 \le 10^3$

[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 2009;

int vout,f[N],g[N],C[N][N],PW2[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int solve(int a, int b, int c) {
if (a < b) swap(a, b);
if (!a && b) return b == c;
int ret = 0;
for (int i=a-b,j,k;i<=c;++i) {
j = i - a + b; k = c - i - j;
if (j >= 0 && k >= 0 && a >= i + k ) {
(ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD;
}
}
return ret;
}

int main() {
PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD;
C[0][0] = 1; for (int i=1;i<N;i++) {
C[0][i] = 1; for (int j=1;j<=i;j++) {
C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
}
}
if (a + b == 0) f[1] = 1;
else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i);
if (c + d == 0) g[1] = 1;
else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i);
for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD;
printf("%d\n",vout);
return 0;
}


## 【HDU 3037】Saving Beans

lucas定理 + 插板法

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

const int MAXN = 100000+9;

int f[MAXN];

char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar();
return ret;
}

inline int quick_pow(int w, int t, int p) {
int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret*w % p;
w = (LL)w*w % p; t >>= 1;
}
return ret;
}

inline int C(int m,int n, int p) {
if (n > m) return 0;
else return (LL)f[m]*quick_pow(f[m-n],p-2,p)*quick_pow(f[n],p-2,p)%p;
}

int lucas(int m, int n, int p) {
if (n == 0) return 1;
else return ((LL)lucas(m/p,n/p,p) * C(m%p,n%p,p)) % p;
}

int main(){
int T = read(); while (T--) {