排课表
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
新学期伊始，作为玉米高中的教务主任W某，又要安排学生们的课程表了。
W某想要知道所有可能的排课表方案，于是他开始在纸上列举所有方案，然而在写满了一摞A4纸后，他发现可能的方案太多了——用尽玉米高中所有的A4纸都写不完。
W某最终放弃了列举所有方案的想法，但他对排课表的方案数产生了兴趣。他的组合数学不太好，所以他找到了正在玉米高中就读的你，请你帮帮TA。
简单地说，玉米高中共有T个班级。
对于其中一个班级i，这个班级每天要上mi节互不相同的课，一共有ni节课可供选择，但这ni节课不能随便安排，其中也有一些限制：
·有ai节课不能安排在第一节上
·有bi节课不能安排在最后一节上
·没有任何一节课既不能在第一节上又不能在最后一节上
你需要求出每个班级排课表的方案数除以998244353的余数。
输入
第1行包含一个正整数T，表示玉米高中的班级数。
第2行到第T+1行，每行包含四个整数，第i+1行的四个整数ni,mi,ai,bi，分别表示班级i可选的课程数，一天的课程数，不能在第一节上的课程数，不能在最后一节上的课程数。
输出
输出T行，第i行表示班级i的排课表方案数除以998244353的余数。
样例输入 Copy
【样例1】
1
3 2 0 1
【样例2】
1
5 3 1 1
样例输出 Copy
【样例1】
4
【样例2】
39
提示
样例1解释
设3节可选的课为a,b,c，其中c不能排在最后一节
4种排课表的方案分别为:ab,ba,ca,cb
所有测试数据满足
·1≤T≤104
·2≤mi≤ni≤105
·ai+bi≤ni
思路：
高中排列组合？ 划掉，忘得一干二净
今天刚学了容斥原理，但是依稀记得高中好像也是这么做的
直接计算方案数并不好算，因为要分类讨论很多种情况，我们不妨逆向思维。
用总的方案数 - a放在第一位的方案数 - b放在第一位的方案数 就可以
真的可以吗？
我们在计算a放在第一位的方案数时，其中有不合法的情况是b在最后一位，同理，我们在计算b放在第一位的方案数时，有不合法的情况是a在第一位，好像减多了呢。
只需要把这一部分加上就可以了~
To be short : 总的方案数-第一节是a的方案数-最后一节是b的方案数+第一节是a而且最后一节是b的方案数
其他的就是高中的知识了
化简过程就不放了~
解释一下第二个式子，其他的都类似：
因为a的位置是确定的，我们首先从a里选出1个放在首位，此时需要选的还有m-1个，能够选的还有n-1个，所以就是从n-1里选m-1个，全排列。
另外，数据较大，需要预处理阶乘和逆元
模板：传送门
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const int mod = 998244353;
ll fact[N];//阶乘
ll infact[N];//逆元
ll ksm(ll a,ll b,ll p){
ll res=1;
while(b){
//&运算当相应位上的数都是1时，该位取1，否则该为0。
if(b&1)
res=1ll*res*a%p;//转换为ll型
a=1ll*a*a%p;
b>>=1;//十进制下每除10整数位就退一位
}
return res;
}
void init(){
fact[0]=1;
infact[0]=1;
for(int i=1;i<N;i++){
fact[i]=fact[i-1]*i%mod;
infact[i]=infact[i-1]*ksm(i,mod-2,mod)%mod;
}
}
int main(){
init();
int t;
cin>>t;
int n,m,a,b;
while(t--){
cin>>n>>m>>a>>b;
ll res=(fact[n]%mod*infact[n-m]%mod-fact[n-1]%mod*infact[n-m]%mod*(a+b)%mod+fact[n-2]%mod*infact[n-m]%mod*a*b%mod)%mod;
if(res<0) res+=mod;
printf("%lld
",res);
}
return 0;
}
玉米田
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
玉米中学的学生社会实践的内容是去玉米田中种玉米。
玉米中学有n块不同的玉米田，这些玉米田编号从1到n，且第i号玉米田与第i+1号玉米田相邻，特殊地，第n号玉米田与第1号玉米田相邻。
现在玉米中学购置了k种不同的玉米，为了美观，学校要求相邻的玉米田中不能种植同一种玉米，现在W某想要知道种植玉米的方案总数。
由于W某耐心有限，因此只需要你求出对20011021取模后的结果即可。
输入
一行两个整数n,k，表示玉米田的数量和玉米的种类数。
输出
加粗样式一行一个整数，表示种植玉米的方案数对20011021取模后的结果。
样例输入 Copy
【样例1】
4 2
【样例2】
4 3
样例输出 Copy
【样例1】
2
【样例2】
18
提示
样例1解释
设2种玉米为a,b
2种种植玉米的方案为:abab,baba
所有数据满足：n,k≤109
直接一波公式：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const ll mod = 20011021;
ll fact[N];//阶乘
ll infact[N];//逆元
ll ksm(ll a,ll b,ll p){
ll res=1;
while(b){
//&运算当相应位上的数都是1时，该位取1，否则该为0。
if(b&1)
res=1ll*res*a%p;//转换为ll型
a=1ll*a*a%p;
b>>=1;//十进制下每除10整数位就退一位
}
return res;
}
void init(){
fact[0]=1;
infact[0]=1;
for(int i=1;i<N;i++){
fact[i]=fact[i-1]*i%mod;
infact[i]=infact[i-1]*ksm(i,mod-2,mod)%mod;
}
}
int main(){
ll n,k;
cin>>n>>k;
ll res=((k-1)*ksm(-1,n,mod)%mod+ksm(k-1,n,mod))%mod;
cout<<res;
return 0;
}