题意： 有k种球，每种球有a[i]个。现在它们都放到一个袋子里，要求取出来的时候，第i种球完全取出来要在第i+1种球前面。问你有多少种取法。 思路： 比赛时没想出来。。。结果其实是很简单的。 倒过来统计就好了。 假设n = sum(a[i]); 首先先看第k种球，如果先把其中一个球放到最后一个位置，那么剩下的a[k]-1个球就是随便放，则有c[n-1][a[k]-1]种放法。

B. Kyoya and Permutation time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Let’s define the permutation of length n as an array p = [p1, p2

Description 给定一张 n 个点 m 条边的无重边无自环的有向图，你要从 1 号点到 n 号点去。 如果你在 t 时刻之后到达n 号点，你要交 x 元的罚款。 每条边从 a i a_i ai​到 b i b_i bi​ ，走过它需要花费 c i c_i ci​元，多次走过同一条边需要多次花费。 走过每条边所需的时间是随机的，对于 k∈[1,t]， p i , k 1 0 5 \d

给定 n n个点mm条边的有向图，起点为 1 1，终点为nn，如果到达时间 >t >t要罚款 x x,通过第i条边的代价是cic_i，以时间 k k经过的概率为pi,k(1≤k≤t)p_{i,k}(1≤k≤t)， ∑pi,k \sum p_{i,k}=1。求最优期望代价。 n≤50,m≤100,t≤2∗105,ci≤106,x≤106. n≤50,m≤100,t≤2*10^5,c_i≤10^6