首页 > 其他分享 >【题解】JLOI2016 - 成绩比较

【题解】JLOI2016 - 成绩比较

时间:2023-11-20 23:13:57浏览次数:34  
标签:JLOI2016 int 题解 ll ans 成绩 sum

【题解】JLOI2016 - 成绩比较

https://loj.ac/p/2026

是我会的题,所以感觉难度不如 noip T3T4。

设 \(f_{i,j}\) 表示考虑到前 \(i\) 门课,有 \(j\) 人被 B 碾压。

转移,设这轮中有 \(k\) 个原本被碾压的人不再被碾压,则相当于从 \(f_{i-1,j+k}\) 转移到 \(f_{i,j}\)。考虑转移系数,首先是 \(j+k\) 人中选 \(k\) 人,现在排名在 B 前面的位置还有 \(r_i-1-k\) 位,所以从 \(n-1-j-k\) 中选 \(r_i-1-k\) 个。最后是每个人有一个分数,易得要乘上 \(\sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}\)。所以转移方程为:

\[f_{i,j} = \sum_{k=0}^{\min(n-j-1,r_i-1)}f_{i-1,j+k}\dbinom{j+k}k\dbinom{n-1-j-k}{r_i-1-k}T_i \]

其中:

\[T_i = \sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1} \]

边界是 \(f_{0,n-1}=1\),答案取 \(f_{m,k}\)。

容易发现瓶颈在于 \(T_i\) 的计算,看到这个式子我们想到了 CF622F,于是直接拉格朗日插值就能求出来了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 110;
const ll P = 1e9 + 7;
int n, m, k, u[N], r[N];
ll f[N][N], y[N*2], t[N], C[N][N];

ll qp(ll x, ll y){
	ll ans = 1;
	while(y){
		if(y & 1){
			ans = ans * x % P;
		}
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

ll lglr(int xk){
	ll res = 0;
	for(int i = 1; i <= n + n; ++ i){
		ll mul = y[i];
		for(int j = 1; j <= n + n; ++ j){
			if(j != i){
				mul = mul * (xk - j + P) % P * qp(i-j+P, P-2) % P;
			}
		}
		res = (res + mul) % P;
	}
	return res;
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; ++ i){
		scanf("%d", &u[i]);
	}
	for(int i = 1; i <= m; ++ i){
		scanf("%d", &r[i]);
	}
	C[0][0] = 1;
	for(int i = 1; i <= n; ++ i){
		C[i][0] = C[i][i] = 1;
		for(int j = 1; j < i; ++ j){
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
		}
	}
	f[0][n-1] = 1;
	for(int i = 1; i <= m; ++ i){
		for(int j = 1; j <= n + n; ++ j){
			y[j] = (y[j-1] + qp(j, n-r[i]) * qp(u[i]-j, r[i]-1)) % P;
		}
		t[i] = lglr(u[i]);
		for(int j = 0; j <= n-1; ++ j){
			for(int k = 0; k <= min(n-j-1, r[i]-1); ++ k){
				f[i][j] = (f[i][j] + f[i-1][j+k] * C[j+k][k] % P * C[n-1-j-k][r[i]-1-k] % P * t[i] % P) % P;
			}
		}
	}
	printf("%lld\n", f[m][k]);
	return 0;
}

标签:JLOI2016,int,题解,ll,ans,成绩,sum
From: https://www.cnblogs.com/KiharaTouma/p/17845161.html

相关文章

  • [题解]CF1899D Yarik and Musical Notes
    思路暴力化简公式题。假定\(b_{i}^{b_j}=b_{j}^{b_{i}}\)成立,那么有:\[2^{a_i\times2^{a_j}}=2^{a_j\times2^{a_i}}\\a_i\times2^{a_j}=a_j\times2^{a_i}\\\frac{a_i}{a_j}=\frac{2^{a_i}}{2^{a_j}}\\\frac{a_i}{a_j}=2^{a_i-a_j}\]因为\(\fra......
  • CF1898 C Colorful Grid 题解
    LinkCF1898CColorfulGridQuestion给出一个\(N\timesM\)的网格图给每一条边染色(R/B),需要存在一条长度为\(K\)的路径从\((1,1)\)到\((N,M)\),路径允许重复通过一个节点。Solution非常有意思的一道题先考虑\(K\)满足的最小值,显然是\((N-1)+(M-1)\),假设走上->......
  • CF1898 B Milena and Admirer 题解
    LinkCF1898BMilenaandAdmirerQuestion给出一个长度为\(n\)的序列\(a\),我们可以做一种操作使得\(a\)非降,操作是:对于一个\(a_i\)选择一个整数\(0\lex\lea_i\),用两个数\(x,(a_i-x)\)来替换\(a_i\)。求最小操作次数。Solution考虑哪些数是需要操作的,如......
  • CF1899 G Unusual Entertainment 题解
    LinkCF1899GUnusualEntertainmentQuestion给出一个排列\(p_i\)和一棵树,给出\(Q\)组询问,每组询问\([L,R,x]\)表示求\(p_L\simp_R\)上是否存在\(p_i\)在\(x\)的字数上。Solution这道题确实是一个好题。我们先考虑一个问题,怎么样才能判断子树,我们给书上的每个......
  • Windows端口占用问题解决
    查询被占用的端口进程8080为端口号netstat-ano|findstr8080杀掉线程14816为进程号taskkill/f/t/im14816......
  • noip2023 题解(民间数据)
    P9868[NOIP2023]词典(民间)直接把每个串\(w_i\)都从大到小/从小到大排一下,记作\(a_i,b_i\)。如果\(b_i\)小于除了\(i\)之外的所有\(a_i\),说明可以,否则不行。求一个前后缀最大值即可。复杂度\(\mathcal{O}(26n+nm)\)。点击查看代码#include<bits/stdc++.h>usingname......
  • 【洛谷 P1125】[NOIP2008 提高组] 笨小猴 题解(字符串+映射+集合)
    [NOIP2008提高组]笨小猴题目描述笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设是单词中出现次数最多的字母的出现次数,是单词中出现次数最少的字母的出现次数,......
  • [ABC326C] Peak 题解
    题目链接题目思路这个问题要求找到一个半开区间,使得在这个区间内包含尽可能多的礼物。首先,我们需要将输入的礼物坐标按照从小到大的顺序进行排序。然后,我们可以使用双指针的方法来寻找最佳的区间。代码以下是代码解释:#include<bits/stdc++.h>usingnamespacestd;constint......
  • [ABC328C] Consecutive 题解
    HelloWorld链接这道题是一个很明显的前缀和,我们把$sum_i$表示为前$i$个字符有多少个有重复,查询的时候就用$sum_{r-1}-sum_{l-1}$就行了。代码#include<bits/stdc++.h>usingnamespacestd;strings;intsum[300010];intmain(){ intn,q; cin>>n>>q>>s; for(in......
  • CF222A Shooshuns and Sequence 题解
    分析这题是一个很水的题,就是对一个序列有$2$种操作方法,一种是对第$K$个数以前的数的第一个进行删除,另一个则是在整个序列后添加这第$K$个数,使得整个序列为同一个数字,显然,后者是无效操作,则只需要判断第$K$个数以后有无与第$K$个不同的数,有则无解,反之有解。若有解,然后再......