2021CCPC威海部分题解
顺序按照难易程度（参考过题⼈数）
-J Circular Billiard Table
题意描述：从圆盘某个边缘以与竖直⽅向夹\(\alpha\)⾓射⼊⼀颗⼩球，⼩球在圆盘内部沿反射规律运动，求解⼩球在第⼀次回到原点之前共发⽣⼏次碰撞
经过分析，我们可知⼩球在反射过程中圆⼼⾓始终保持不变，⽽我们这个圆⼼⾓\(\theta=2\alpha\)显然，所以我们可以得知⼩球反射\(n\)次回到原点，⼀定有\
(n\cdot\theta=k\cdot360\)，其中\(k\)为某个正整数
所以我们需要求解最⼩的\(n\)满⾜有\(360|n\theta\)
⽽要求解\(a|n*b\)的最⼩正整数\(n\)，我们可知\(n=\frac{a}{gcd(a,b)}\)
将数值代⼊上述公式后即可求解
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T,a,b;
int prime[1000005];
int cnt=0;
vector<int> ans;
int div(int x){
for(int i=1;i<=cnt;i++){
if(x==1)break;
if(x%prime[i]){
x/=prime[i];
ans.push_back(prime[i]);
i-=1;
}
}
}
int main(){
//cout<<__gcd(50,360)<<endl;
cin>>T;
while(T--){
scanf("%lld %lld",&a,&b);
ll x=b*180;
/
/ int i;
// for(i=1;;i++){
//    if(i*a % x==0)break;
// }
// cout<<i-1<<endl;
cout<<(x/__gcd(a,x))-1<<endl;
}
return 0;
}
-D Period
题意描述：规定⼀个整数\(T\)，如果其是字符串\(s\)的⼀个\(period\)当且仅当对于任意\(i\in (T,|s|]\)，均
有\(s[i]=s[i-T]\)并且有\(1\le T\le |s|\)，我们给定⼀个只包含⼩写字母的字符串，并且给定\(q\)个询问，每个询问将字符串的某个位置修改为#，且修改之间相互独⽴，求当前修改情况下字符串的\(period\)数
本题中所有的询问都只有字符串中的⼀个位置改变，针对题⽬内容询问处理相对容易，我们先对原字符串进⾏预处理，通过预处理结果与修改位置我们可以得到每次询问的答案。
所以本题的关键在于如何进⾏预处理，题⽬中的\(period\)⾃然让我们联想到\(kmp\)算法，我们可以先求出原字符串的\(next\)数组，再借助\(next\)数组做进⼀步的求解
得到\(next\)数组之后，因为原字符串中第\(i\)位应该对应\(next\)数组中的第\(i-1\)位，所以我们初始化上界的值应该为\(j=len\)，随后我们借助\(next\)数不断向前回溯，做\ (j=nex[j]\)，对于\(nex[j]!=0\)，我们可以说明该字符串存在⼀个长度为\(nex\)的\(period\)
我们对于出现过的回溯过程中出现过的\(nex[j]\)做统计，最后计算前缀和数组\(a[i]\)表⽰字符串有多少个长度在\(i\)以内的\(period\)
对于当前修改位置\(x\)的字母为#，显然长度⼤于等于\(x\)的\(period\)都显然不再能够称为\(period\)，但因为\(period\)的长度是同时从队⾸元素和队尾元素考虑的，所以我们针对\ (x\)限制长度时也需要从队⾸队尾分别考虑，我们做\(x=min(x-1,len-x)\)，得到的\(x\)显然就是上限长度，直接代⼊数组\(a\)就是当前询问的答案
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
char s[maxn];
int q,len;
int nex[maxn],a[maxn];
// aabaaba
// 如何对period进⾏求解
void Getnext(){
int j=0,k=-1;
nex[0]=-1;
while(j<=len-1){
if(k==-1||s[j]==s[k]){
j++;
k++;
nex[j]=k;
}else{
k=nex[k]; //向前回溯
}
}
void prenext(){
int j=len;
while(j>0){
a[nex[j]]+=1;
j=nex[j];
}
a[0]=0;
for(int i=1;i<=len-1;i++){
a[i]+=a[i-1];
}
}
int main(){
scanf("%s",s);
len=strlen(s);
Getnext();
prenext();
scanf("%d",&q);
// 先对字符串进⾏预处理
// 通过数组记录来处理询问相关操作
for(int i=1;i<=len;i++){
cout<<nex[i]<<' ';
}
cout<<endl;
for(int i=1;i<=len;i++){
cout<<a[i]<<' ';
}
// cout<<nex[3]<<endl;
// cout<<nex[len-1]<<endl;
while(q--){
int x;
scanf("%d",&x);
x=min(x-1,len-x);
printf("%d\n",a[x]);
}
return 0;
}
-G Desserts
题意描述：有\(n\)件物品，每件物品有\(a[i]\)件，我们需要将这\(n\)件物品全部分给⾄多\(m\)个⼈，每个⼈每种物品⾄多只能拿⼀件，求对于范围\([1,m]\)内每种⼈数的分配⽅案数朴素思想：易知，只有当分配⼈数⼤于\(n\)种物品中最⼤件数时，才能完全分配完所有产品，因此⽅案数才不为0。此时对于第\(i\)件产品，我们显然有\(C_{t}^{a[i]}\)种分配策略，其中\(t\)为当前的⼈数，满⾜\(1\le t\le m\)，此时我们只需要将所有产品的分配策略相乘即可得到在当前⼈数下的分配⽅案总数，时间复杂度为\(O(mn)\)，显然会发⽣超时，所以我们接下来需要思考如何优化时间复杂度
优化（本题最难想到的点）：我们注意到题⽬中有条件\(\sum^n_{i=1}a_i\le 10^5\)，所以我们可以知道对于\(n\)个\(a_i\)，我们最多仅能有\(\sqrt{2*10^5}\)个\(a_i\)互异\((\frac{n(n-
1)}{2}\le10^5)\)，我们能够使⽤\(unordered\_set\)记录下所有不同的\(a[i]\)及其出现次数，对于出现多次的\(a[i]\)我们使⽤快速幂算法处理即可，最后在不同的⼈数下下将\
(unordered\_set\)中每个\(a_i'\)的结果计算并相乘即可得到最终结果。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define ll long long
const int maxn = 5e4+5;
const int M = 1e5+5;
int n,m;
int a[maxn],cnt[maxn]; // 后者⽤来记录a_i相同数字出现的次数
unordered_set<int> at; // ⽤来记录去重之后的a数组
// 暴⼒枚举 O(nm) 显然超时
// 所以本题的关键在于如何快速进⾏计算
ll exp(ll a,ll b){
ll tmp=1;
while(b){
if(b&1)tmp=(a*tmp)%mod;
a=(a*a)%mod;
b/=2;
}
return tmp%mod;
}
ll fac[M],finv[M];
ll inv(ll x){
return exp(x,mod-2);
fac[i]=fac[i-1]*i%mod;
}
finv[M-5]=inv(fac[M-5]);
for(int i=M-6;i>=0;i--){
finv[i]=finv[i+1]*(i+1)%mod;
}
}
ll C(ll n,ll m){ // 快速计算
if(m>n)return 0;
return fac[n]*finv[m]%mod*finv[n-m]%mod;
}
int main(){
init();
cin>>n>>m;
int maxx=0;
for(int i=1;i<=n;i++){
cin>>a[i];
maxx=max(maxx,a[i]);
}
for(int i=1;i<=n;i++){
cnt[a[i]]++;
at.insert(a[i]);
}
for(int i=1;i<=m;i++){
if(i<maxx){ // ⽆法完全分配
printf("0\n");
continue;
}
ll ans=1;
for(auto x:at){
ans=(ans*exp(C(i,x),cnt[x]))%mod;
}
printf("%lld\n",ans); // 输出量较⼤，使⽤printf
}
return 0;
}
-M 810975
参考题解：
在完成这道题以前我们先考虑⼀道题⽬
HDU 6397
题意描述：给定\(n,m,k\)，要求我们选定\(m\)个范围在\([0,n-1]\)中的数，使得这\(m\)个数的和为\(k\)
我们先在选定数⽆上限的条件下考察该问题，显然我们可以将\(k\)看作\(k\)个\(1\)，我们通过\(m-1\)个隔板来将这\(k\)个\(1\)划分为\(m\)个数，但由于数字可以取\(0\)，⽽隔板法显然不能够满⾜数字选\(0\)的需求，此时我们可以做⼀个等价处理，将选取的\(m\)个数的下限都加\(1\)，保障其不能取\(0\)，这样我们
所有数的和应该为\(k+m\)，所以我们使⽤隔板法可以知道⽅法数应该为\(C_{k+m-1}^{m-1}\)
接下来我们考虑有选取的\(m\)限制的情况，我们已知⽆限制情况下的⽅案总数，所以我们可以利⽤容斥原理来考虑有限制情况下的⽅案总数
借助容斥原理，问题转化为求解选择\(m\)个数，其中⾄少有\(i\)个数⼤于\(n-1\)，且\(m\)个数的和为\(k\)的⽅案总数。要实现⾄少有\(i\)个数⼤于等于\(n\)，我们可以将不限定\([0,n-1]\)区间选择出来的\(m\)个数其中的\(i\)个数分别加上\(n\)，保障这些数⼀定满⾜⼤于\(n\)，⽽此时我们选择的数据总和应该为\(k-n*i\)，以保障增加之后数据之和为\(k\)，利⽤我们考虑⽆上限情况时的⽅法，我们可以知道情况数应该为\(C_{m}^i\times C_{k+m-1-n}^{m-1}\)。
记有⾄少\(i\)个数⼤于\(n-1\)为的情况总数为\(f(i)\)，则所求结果应当为\(f(0)-f(1)+f(2)-\cdots+f(t)\)，其中\(t=min(n,k/n)\)
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e6+5;printf怎么加endl
const int mod = 998244353;
int T,n,m,k;
ll qsm(ll a,ll b){
ll tmp=1;
while(b){
if(b&1)tmp=(tmp*a)%mod;
a=a*a%mod;
b/=2;
}
return tmp;
}
ll fac[M],finv[M];
ll inv(ll x){
return qsm(x,mod-2);
}
fac[i]=fac[i-1]*i%mod;
}
finv[M-5]=inv(fac[M-5]);
for(int i=M-6;i>=0;i--){
finv[i]=finv[i+1]*(i+1)%mod;
}
}
ll C(ll n,ll m){ // 快速计算
if(m>n)return 0;
return fac[n]*finv[m]%mod*finv[n-m]%mod;
}
int main(){
init();
cin>>T;
while(T--){
cin>>n>>m>>k;
int f=1;
int ans=0;
for(int i=0;i<=m;i++){
int tmp=1;
if(!f)tmp=mod-1; // 1的
f^=1;
if(1ll*i*n>k+m-1)break;
ans=(1ll*ans+1ll*tmp*C(m,i)%mod*C(k+m-1-i*n,m-1)%mod);
}
}
return 0;
}
接下来让我们回到题⽬本⾝
CCPC Weihai -M 810975
题意描述：给定\(n,m,k\)，要求构造长度为\(n\)的\(01\)串，其中有且仅有\(m\)个\(1\)，且连续\(1\)段落的最⼤长度恰为\(k\)，求满⾜条件的\(01\)串总数
本题要求串中连续\(1\)段落的最⼤长度恰好为\(k\)，我们此处可以使⽤容斥原理，考虑连续\(1\)段落上限为\(k\)的情况和连续\(1\)段落上限为\(k-1\)的情况，并利⽤前者减去后者即可所以接下来我们考虑的问题即是求满⾜长度为\(n\)，\(1\)个数为\(m\)，且连续\(1\)段落上限为\(k\)的\(01\)串数⽬
本题中的\(0\)我们可以视为隔板，利⽤\(0\)来将\(1\)划分为不同的连续段落，⽽因连续\(1\)段落的上限为\(k\)，所以我们可以知道任意两个\(0\)之间\(1\)的数量的取值范围应该为\ ([0,k]\)，并且我们可以知道所有连续\(1\)段落的和应该为\(m\)
如此我们可以将问题转化为选取\(n-m+1\)个数，要求这\(n-m+1\)个数的取值范围在\([0,k]\)，并且总和为\(n\)
这样本题求解的问题可以直接类⽐到HDU 6397当中，结合其中的分析过程我们可以得到的代码
当然需要注意上⾯题⽬中的取值界限\(n\)要求不能取到⽽本题中取值界限\(k\)要求可以取到，需要做适当的转化
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
const int M = 1e5+5;
// 有m个1，n-m个0，求最⼤1连续长度恰好为5的01串个数
// 7个1 2个0 长度限定5
//
ll qsm(ll a,ll b){
ll tmp=1;
while(b){
if(b&1)tmp=(tmp*a)%mod;
a=a*a%mod;
b/=2;
}
return tmp;
}
ll fac[M],finv[M];
ll inv(ll x){
return qsm(x,mod-2);
}
void init(){
fac[0]=1;
for(int i=1;i<=M-5;i++){
fac[i]=fac[i-1]*i%mod;
}
finv[M-5]=inv(fac[M-5]);
for(int i=M-6;i>=0;i--){
finv[i]=finv[i+1]*(i+1)%mod;
}
}
ll C(ll n,ll m){ // 快速计算
if(m>n)return 0;
return fac[n]*finv[m]%mod*finv[n-m]%mod;
}
ll cal(ll num,ll sum,ll up){
int f=1;
ll ans=0;
for(int i=0;i<=num;i++){
int tmp=1;
if(!f)tmp=mod-1;  // ⽤于做减法运算
f^=1;
if(i*up>sum+num-1)break;
ans=(ans+tmp*C(num,i)%mod*C(sum+num-1-i*up,num-1)%mod)%mod;        //cout<<ans<<endl;
}
return ans;
}
int main(){
init();
int n,m,k;
cin>>n>>m>>k;
cout<<(cal(n-m+1,m,k+1)-cal(n-m+1,m,k)+mod)%mod<<endl;
//cout<<cal(n-m+1,m,k)<<endl;
//cout<<cal(m,n-m+1,k)<<endl;
return 0;
}
// 靠左、中间、靠右
// 任何连续1段落必须包含在两个0之间或者边缘与1个0之间
// 我们可以在零⼀串的⾸位加上两个哨兵0，则所有的连续1段落都在0之中
// 原题中存在 n-m个0 ，则可以存在n-m+1个1段落
// 将m个1在这n-m+1个段落中进⾏分配
//