补题大赛!
"现在就是把之前欠下的债还清的时刻了!"
loveJY:QAQ
题解已经很详细了所以我们以存放代码为主
P3239 [HNOI2015]亚瑟王
坑点:清空ans,以及注意这个i和r取min
#include<bits/stdc++.h>
#define db double
using namespace std;
const int MAXN = 500;
int T, n, r;
int d[MAXN];
db f[MAXN][MAXN], ans, p[MAXN];
inline db ksm(db x, int y) {
db ans = 1;
while(y) {
if(y & 1)ans = ans * x;
x = x * x;
y >>= 1;
}
return ans;
}
int main() {
scanf("%d", &T);
while(T-- > 0) {
scanf("%d%d", &n, &r);
for(int i = 1; i <= n; ++i)scanf("%lf%d", &p[i], &d[i]);
f[0][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= min(i, r); ++j) {
if(j)
f[i][j] += f[i - 1][j - 1] * (1 - ksm(1 - p[i], r - j + 1));
f[i][j] += f[i - 1][j] * ksm(1 - p[i], r - j);
}
}
ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < min(i, r); ++j) {
ans += f[i - 1][j] * (1 - (ksm(1 - p[i], r - j))) * d[i];
}
}
printf("%.8lf\n", ans);
memset(f, 0, sizeof(f));
}
return 0;
}
P5516 [MtOI2019]小铃的烦恼
其实题解代码都很短,我手写线性高消被教训了QAQ
- 注意高消还是要交换那些0项的,i个i+1交换,比较fabs啊
- 回代和消元的时候都要特判n+1项要不要额外搞
#include<bits/stdc++.h>
using namespace std;
#define db double
const int MAXN = 2e3 + 7;
const db eps = 1e-9;
char s[MAXN];
int a[MAXN], n;
db f[MAXN][MAXN];
//线性高消
//i消掉i+1,可以得到第n项
//回代的时候,i+1回代i即可!!
inline void out() {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n + 1; ++j) {
printf("%.4lf ", f[i][j]);
}
puts("");
}
}
inline void guass() {
for(int i = 1; i < n; ++i) {
if(fabs(f[i][i]) < fabs(f[i + 1][i])) {
for(int j = i - 1; j <= i + 2; ++j)swap(f[i][j], f[i + 1][j]);
if(i != n - 1)swap(f[i + 1][n + 1], f[i][n + 1]);
}
db kk = f[i][i];
assert(fabs(kk) >= eps);
for(int j = i - 1; j <= i + 1; ++j)f[i][j] /= kk;
f[i][n + 1] /= kk;
kk = f[i + 1][i];
for(int j = i; j <= i + 2; ++j)f[i + 1][j] -= kk * f[i][j];
if(i != n - 1)f[i + 1][n + 1] -= kk * f[i][n + 1];
}
//得到一个没有回代的矩阵
for(int i = n; i >= 2; --i) {
db kk = f[i][i];
for(int j = i - 1; j <= i + 1; ++j)f[i][j] /= kk;
if(i != n)f[i][n + 1] /= kk;
kk = f[i - 1][i];
for(int j = i; j >= i - 2; --j)f[i - 1][j] -= kk * f[i][j];
f[i - 1][n + 1] -= kk * f[i][n + 1];
}
return ;
}
inline void init() {
f[1][1] = -1;
f[1][n + 1] = -0.5 * n;
f[1][2] = 1;
for(int i = 2; i < n; ++i) {
f[i][i] = -1;
f[i][i - 1] = (i - 1) / ((db)2 * i);
f[i][i + 1] = (i + 1) / ((db)2 * i);
f[i][n + 1] = -1 * n * (n - 1) / (db)(2 * i * (n - i));
}
f[n][n] = 1;
f[n][n + 1] = 0;
return ;
}
inline void solve() {
db ans = 0;
for(int i = 0; i < 26; ++i)ans += f[a[i]][n + 1] * a[i] / n;
printf("%.1lf\n", ans);
return ;
}
int main() {
scanf("%s", s);
n = strlen(s);
for(int i = 0; i < n; ++i)a[s[i] - 'A']++;
init();
guass();
solve();
return 0;
}
P7245 灯光效果
因为dy的下标写成iWA了几发
小心m不是longlong
//终于取模了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6 + 7;
const ll P = 998244353;
const ll inv2 = (P + 1) / 2;
int n, m, k;
int dx[MAXN], dy[MAXN];
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline void add(ll &x, ll y) {
x += y;
if(x >= P)x -= P;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; ++i)scanf("%d", &dx[i]);
for(int i = 1; i <= m; ++i)scanf("%d", &dy[i]);
ll ans = (1ll * m * (m - 1) % P * inv2 % P);
ll Pm = ksm(ans * ans % P, P - 2);
ans = 0;
for(int i = 1; i < m; ++i) {
for(int j = 1; j < m; ++j) {
ll qwq = 1ll * i * (m - i) % P * j % P * (m - j) % P * Pm % P;
ll qaq = (inv2 - ksm((1 - 2 * qwq % P + P) % P, k) * inv2 % P + P) % P;
add(ans, qaq * (1ll * dx[i + 1] - dx[i]) % P * (1ll * dy[j + 1] - dy[j]) % P);
}
}
printf("%lld\n", ans);
return 0;
}
P5405 [CTS2019]氪金手游
毒瘤啊!
其实并不难调,因为我抄的题解qwq
细节小心自然溢出,这个a可能很大QAQ
然后就是这个背包卷积要*3
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXN = 4e3 + 7;
int n, ccnt;
int a[MAXN][4], siz[MAXN];
ll f[MAXN][MAXN], ans, inv[MAXN], t[MAXN];
int home[MAXN], nxt[MAXN], to[MAXN], w[MAXN];
inline void add(ll &x, ll y) {
x += y;
if(x >= P)x -= P;
}
inline void ct(int x, int y, int z) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
w[ccnt] = z;
}
inline ll ksm (ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
//这里容斥
//相当于枚举那些边至少是反向的
//至少没有是正向边
//那么考虑一个正向边,我们系数就要乘-1
//然后考虑不选,随意,我们没有关系啊,没有
//记录子树和,进行转移即可QAQ
//注意我们的容斥式子是
//\sum_{S \in T}(-1)^{|S|}\frac{p}{sum}
//p是概率,sum是权值和Qaq
//求出方案数*权值即可
inline void dfs(int u, int F) {
f[u][1] = 1ll * a[u][0] * a[u][3] % P; //显然qaq
f[u][2] = 1ll * a[u][1] * a[u][3] % P * 2 % P;
f[u][3] = 1ll * a[u][2] * a[u][3] % P * 3 % P;
siz[u] = 1;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F)continue;
dfs(v, u);
for(int q = 1; q <= siz[u] * 3; ++q) {
for(int p = 1; p <= siz[v] * 3; ++p) {
if(!w[i]) {
add(t[p + q], P - f[u][q] * f[v][p] % P);
add(t[q], f[u][q] * f[v][p] % P);
} else {
add(t[p + q], f[u][q] * f[v][p] % P);
}
}
}
siz[u] += siz[v];
for(int p = 1; p <= 3 * siz[u]; ++p) {
f[u][p] = t[p];
t[p] = 0;
}
}
for(int i = 1; i <= siz[u] * 3; ++i) {
f[u][i] = 1ll * f[u][i] * inv[i] % P;
}
return ;
}
ll fac[MAXN], ifac[MAXN];
inline void init() {
int N = 4 * n;
fac[0] = 1;
for(int i = 1; i <= N; ++i)fac[i] = fac[i - 1] * i % P;
ifac[N] = ksm(fac[N], P - 2);
for(int i = N - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
ifac[0] = 1;
for(int i = 1; i <= N; ++i)inv[i] = ifac[i] * fac[i - 1] % P;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]), a[i][3] = ksm(a[i][1] + a[i][0] + a[i][2], P - 2);
for(int i = 1, x, y; i < n; ++i)scanf("%d%d", &x, &y), ct(x, y, 1), ct(y, x, 0); //x在y前面QAQ
init();
dfs(1, 0);
for(int i = 1; i <= 3 * n; ++i)add(ans, f[1][i]);
printf("%lld\n", ans);
return 0;
}
/*
3
0 0 1
0 1 0
1 0 0
1 2
3 2
*/
CF961G Partitions
一开始zhq的式子是错的,害了我/kk
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 4e5 + 7;
const int P = 1e9 + 7;
int n, K;
int w[MAXN];
ll fac[MAXN], ifac[MAXN];
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline void add(ll &x, ll y) {
x += y;
if(x >= P)x -= P;
}
inline void init() {
fac[0] = ifac[0] = 1;
for(int i = 1; i <= K; ++i)fac[i] = fac[i - 1] * i % P;
ifac[K] = ksm(fac[K], P - 2);
for(int i = K - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
}
int main() {
scanf("%d%d", &n, &K);
for(int i = 1; i <= n; ++i)scanf("%d", &w[i]);
if(n == 1) {
printf("%d\n", w[1]);
return 0;
}
init();
ll ans = 0;
for(int i = 0; i <= K - 1; ++i) {
ll tmp = (n - 1) * ksm(K - i, n - 2) % P + ksm(K - i, n - 1);
tmp %= P;
if(i & 1)add(ans, P - ifac[i] * ifac[K - i - 1] % P * tmp % P);
else add(ans, ifac[i] * ifac[K - i - 1] % P * tmp % P);
}
ll qwq = ans;
ans = 0;
for(int i = 1; i <= n; ++i)add(ans, qwq * w[i] % P);
printf("%lld\n", ans);
return 0;
}
P3886 [JLOI2009]神秘的生物
头插DP之最小表示法
调出来纯靠运气
有两个锅,第一个是home数组开小了
第二个是upd写错了,把都是0也算进去了
第三个是trs2函数调用vis后没有清空
#include<bits/stdc++.h>
#define pii pair<int,int>
#define se second
#define fi first
using namespace std;
const int MAXN = 11;//qwq???
const int MAXS = (1 << 21);
const int P = 19260817;
//总状态数2^27=134217728 /xyx
int n, a[MAXN][MAXN], ccnt, cnt, tot, vis[MAXN], bits[MAXN], ans;
pii que[MAXS], rc[MAXS];
int home[P], to[MAXS], nxt[MAXS], w[MAXS];
//插头dp啊
//用个hash存一下,懒得写的麻烦了?...qaq
inline void ct(int x, int y, int z) {
ccnt++;
assert(ccnt <= MAXS);
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
w[ccnt] = z;
que[++tot].fi = ccnt;//记下来了,这条边!
que[tot].se = x;
}
inline void ins(int sta, int x) {
int u = sta % P;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == sta) {
w[i] = max(x, w[i]);
return;
}
}
ct(u, sta, x);
return;
}
inline void initH() {
cnt = tot;
ccnt = 0;
for(int i = 1; i <= tot; ++i) {
home[que[i].se] = 0;
rc[i].fi = to[que[i].fi];
rc[i].se = w[que[i].fi];
}//我们无需清空这些的信息啊!
tot = 0;
return ;
}
//新建颜色转移
inline void trs2(int sta, int j, int v) {
for(int i = 0; i < n; ++i) {
vis[(sta >> bits[i] & 7)]++;
}
int gt = 0;
for(int i = 1; i < 8; ++i)
if(!vis[i]) {
gt = i;
break;
}
for(int i = 0; i <= 8; ++i)vis[i] = 0;
ins(sta ^ (gt << bits[j - 1]), v);
return ;
}
//合并颜色转移
inline void trs3(int sta, int j, int v) {
int qwq = sta >> bits[j - 1] & 7;
int qaq = sta >> bits[j - 2] & 7;
for(int i = 0; i < n; ++i) {
if((sta >> bits[i] & 7) == min(qwq, qaq)) {
sta ^= (((sta >> bits[i] & 7)^max(qwq, qaq)) << bits[i]);
}
}
ins(sta, v);
return;
}
//上向下转移
inline void trs1(int sta, int i, int j, int val, int opt) {
int QAQ = 0, qwq = sta >> bits[j - 1] & 7;
for(int i = 0; i < n; ++i) {
if((sta >> bits[i] & 7) == qwq)++QAQ;
}
if(opt == 1) {//选?
ins(sta, val + a[i][j]);
} else {
if(QAQ <= 1)return ;//不合法转移
ins(sta ^ (qwq << bits[j - 1]), val);
}
return;
}
inline void upd(int sta, int v) {
for(int i = 0; i < n; ++i) {
vis[(sta >> bits[i] & 7)]++;
}
int QAQ = 0;
for(int i = 1; i < 8; ++i)
if(vis[i]) {
QAQ++;
vis[i] = 0;
}
if(QAQ != 1)return ;//必须要有啊
ans = max(ans, v);
}
inline void touchadp() {
//0表示未连通
//然后有1,2,3,4,5种颜色
ins(0, 0); //插入一个0,0
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
initH();
for(int k = 1; k <= cnt; ++k) {
int sta = rc[k].fi;
int val = rc[k].se;
int upu = (sta >> bits[j - 1] & 7);
if(j == 1) {
if(upu) {
trs1(sta, i, j, val, 1); //第一类转移,上面的颜色单独传下来,包括选和不选!!
trs1(sta, i, j, val, 0);
} else {
trs2(sta, j, val + a[i][j]); //新开颜色
ins(sta, val);//不开颜色
}
continue;
}
int upl = (sta >> bits[j - 2] & 7);
if(upu && upl) {//都有颜色
if(upu != upl) {
trs3(sta, j, val + a[i][j]);//颜色合并
trs1(sta, i, j, val, 0);//不选
} else {//颜色相同
ins(sta, val + a[i][j]);//选!
ins(sta ^ (upu << bits[j - 1]), val);//不选!!
}
} else if(upl) {
ins(sta ^ (upl << bits[j - 1]), val + a[i][j]);//只有左边有颜色,焊接
ins(sta, val);//放弃
} else if(upu) {//只有上方有颜色
trs1(sta, i, j, val, 1);//选
trs1(sta, i, j, val, 0);//不选
} else {//都 没 有 颜 色
trs2(sta, j, val + a[i][j]);//新开颜色
ins(sta, val);//不要了
}
upd(sta, val); //更新答案
}
}
}
initH();
for(int k = 1; k <= cnt; ++k) {
upd(rc[k].fi, rc[k].se);
}
//答案怎么统计啊QAQ
//相当于只有一个颜色的statue,他们已经连通了,然后算个答案就好了
printf("%d\n", ans);
return ;
}
inline int tp() {
ans = -1e9;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(a[i][j] > 0)return 0;
ans = max(ans, a[i][j]);
}
}
printf("%d\n", ans);
return 1;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
scanf("%d", &a[i][j]);
}
}
if(tp())return 0;
for(int i = 0; i < n; ++i)bits[i] = i * 3;
touchadp();
return 0;
}
CF1327F AND Segments
早该写了QAQ
//简单动态规划????QAQAQ
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 7;
const int P = 998244353;
ll ans;
int n, k, m;
int lx[MAXN], rx[MAXN], vx[MAXN];
int f[MAXN], vis[MAXN], lim[MAXN];
inline void add(int &x, int y) {
x += y;
if(x >= P)x -= P;
}
inline int solve(int x) {
for(int i = 1; i <= m; ++i) {
if(vx[i] >> x & 1) {
vis[lx[i]]++;
vis[rx[i] + 1]--;
continue;
}
lim[rx[i]] = max(lx[i], lim[rx[i]]);
//至少有0
}
for(int i = 1; i <= n; ++i)
vis[i] += vis[i - 1];
int p = 0;//0号放了可爱的点
f[0] = 1;
int sum = 1;//可爱全局和
for(int i = 1; i <= n; ++i) {
f[i] = 0;
if(vis[i])
f[i] = 0;
else {
f[i] = sum;
add(sum, f[i]);
}
vis[i] = 0;
while(p < lim[i]) {
add(sum, P - f[p]);
++p;
}
}
for(int i = 1; i <= n; ++i)lim[i] = 0;
//考虑我们最后答案是什么呢?
return sum;
}
int main() {
scanf("%d%d%d", &n, &k, &m);
for(int i = 1; i <= m; ++i)scanf("%d%d%d", &lx[i], &rx[i], &vx[i]);
ans = 1;
for(int i = 0; i < k; ++i)ans = ans * solve(i) % P;
printf("%lld\n", ans);//每一位的方案数乘起来!
return 0;
}
P4229 某位歌姬的故事
毒瘤DP,一个点是一个区间
注意转换为左闭右开方便处理QAQ
然后加入点1,点n方便
然后特判要小心翼翼QAQ,是判断一个区间的mx至少要有一个达到啊
//感觉有一车细节QAQ
//勇一下
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int MAXN = 1550;
const int P = 998244353;
int T, n, Q, A;
map<int, int> mp;
ll ans;
int l[MAXN], r[MAXN], m[MAXN], len[MAXN], lim[MAXN], mx[MAXN];
std::vector<int> v;
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
inline void init() {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i = 1; i <= Q; ++i) {
l[i] = getid(l[i]);
r[i] = getid(r[i]) - 1;
}
// 考虑离散化,相当于排序后的数组上,对于第i个点,对应v[i]~v[i+1]-1
for(int i = 0; i < (int)v.size(); ++i) {
if(i == (int)v.size() - 1) {
len[i + 1] = n - v[i] + 1;
} else
len[i + 1] = v[i + 1] - v[i];
}
n = v.size();
//于是你会发现这个限制相当于[l+1,r-1]的离散后的点上!
return ;
}
inline int pd() {
for(int i = 1; i <= Q; ++i) {
bool flg = 1;
for(int j = l[i]; j <= r[i]; ++j) {
if(mx[j] >= m[i]) {
flg = 0;
break;
}
}
if(flg)return 1;
}
return 0;
}
inline int init3() {
//包括他的一定不会更严(小于他)
//那么对于这个点来说,我们应该取所有限制的最小值
//而限制的最小值就相当于对于一个右端点,左端点的最大值啊!
//QAQ
for(int i = 1; i <= Q; ++i)
for(int j = l[i]; j <= r[i]; ++j)
mx[j] = min(mx[j], m[i]);
for(int i = 1; i <= Q; ++i) {
int R;
for(R = r[i]; R >= l[i]; --R)
if(mx[R] == m[i])break;
int L;
for(L = l[i]; L <= r[i]; ++L)
if(mx[L] == m[i])break;
lim[R] = max(L, lim[R]);//挂在限制区间右端点上???
}
return 0;
}
int f[MAXN][MAXN];
inline void init2() {
mp.clear();
memset(f, 0, sizeof(f));
for(int i = 1; i <= n; ++i)lim[i] = 0, mx[i] = A + 1;//说不定就没限制了!
return ;
}
inline void add(int &x, int y) {
x += y;
if(x >= P)x -= P;
}
inline ll solve(int x) {
f[0][0] = 1;
int lst = 0;
for(int i = 1; i <= n; ++i) {
if(mx[i] != x)continue;//没用啊
for(int j = lim[i]; j <= i; ++j) {
if(mx[j] != x && j != 0)continue; //不连续的存在~
if(i == j) {
if(mx[i] == A + 1)continue;
ll t = (ksm(mx[i], len[i]) - ksm(mx[i] - 1, len[i]) + P) % P;
for(int k = 0; k <= i; ++k) {
add(f[i][i], f[lst][k] * t % P);
}
continue;
}
f[i][j] = f[lst][j] * ksm(mx[i] - 1, len[i]) % P;
}
lst = i;
}
int ans = 0;
for(int i = 0; i <= lst; ++i)add(ans, f[lst][i]);
return ans;
}
int main() {
scanf("%d", &T);
while(T-- > 0) {
scanf("%d%d%d", &n, &Q, &A);
v.clear();//清空啦!
v.pb(1);
v.pb(n);
for(int i = 1; i <= Q; ++i)scanf("%d%d%d", &l[i], &r[i], &m[i]), r[i]++, v.pb(l[i]), v.pb(r[i]);
//这里变成左闭右开才好处理QaQ
init();//离散化
init2();
init3();
if(pd()) {
puts("0");
continue;
}
ans = 1;
for(int i = 1; i <= Q; ++i) {
if(mp.find(m[i]) == mp.end()) {
ans = ans * solve(m[i]) % P; //DP
mp[m[i]] = 1;
}
}
if(mp.find(A + 1) == mp.end())ans = ans * solve(A + 1) % P;
printf("%lld\n", ans);
}
return 0;
}
/*
1
7 3 74
3 6 56
2 5 56
3 7 70
*/
AT5202 [AGC038E] Gachapon
容斥dp的精华在于照着式子统计容斥系数吧qwq
小心式子别抄错了QAQ
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXN = 405;
int n, a[MAXN], b[MAXN];
ll fac[3 * MAXN], ifac[3 * MAXN], inv[MAXN][MAXN];
int f[MAXN][MAXN][MAXN];//容斥DP
//前i个数,然后a的和,c的和
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline void add(int &x, int y) {
x += y;
if(x >= P)x -= P;
}
inline void init() {
int mx1 = 0, mx2 = 0, N = 0;
for(int i = 1; i <= n; ++i) {
mx1 = max(a[i], mx1);
mx2 = max(mx2, b[i]);
N += max(a[i], b[i]);
}
for(int i = 1; i <= mx1; ++i) {
for(int j = 0; j <= mx2; ++j) {
inv[i][j] = ksm(i, j);
}
}
fac[0] = 1;
ifac[0] = 1;
for(int i = 1; i <= N; ++i)
fac[i] = fac[i - 1] * i % P;
ifac[N] = ksm(fac[N], P - 2);
for(int i = N - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
return ;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i], &b[i]);
}
init();
f[0][0][0] = P - 1;
ll Sa = 0, Sb = 0;
for(int i = 1; i <= n; ++i) {
Sa += a[i];
Sb += b[i];
for(int j = 0; j <= Sa; ++j) {
for(int k = 0; k <= Sb; ++k) {
//选择这个数
if(j - a[i] >= 0)
for(int l = 0; l < b[i]; ++l) {
if(k - l >= 0)
add(f[i][j][k], P - 1ll * f[i - 1][j - a[i]][k - l] * inv[a[i]][l] % P * ifac[l] % P);
//ifac是i!的逆元
}
add(f[i][j][k], f[i - 1][j][k]);//不选择这个数,没有变化
}
}
}
int ans = 0;
for(int i = 0; i <= Sa; ++i) {
ll tmp = Sa * ifac[i] % P * fac[i - 1] % P;
for(int j = 0; j <= Sb; ++j) {
add(ans, tmp * f[n][i][j] % P * fac[j] % P * ksm(ifac[i] * fac[i - 1] % P, j) % P);
}
}
printf("%d\n", ans);
return 0;
}