CSP模拟15
T1 CF1850G The Morning Star
水题 但是考场写挂了
直接写阶乘会 \(RE\)（这里\(A\)阶乘可以优化成两个数相乘）
可以分解为4种不同斜率的直线用 \(map\) 存（
点击查看代码
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
#define ll long long
ll ans;
ll n,si1,si2,si3,si4;
ll num1[200010],num2[200010],num3[200010],num4[200010];
int work(){
for(int i=1;i<=si1;i++){
num1[i]=0;
}
for(int i=1;i<=si2;i++){
num2[i]=0;
}
for(int i=1;i<=si3;i++){
num3[i]=0;
}
for(int i=1;i<=si4;i++){
num4[i]=0;
}
si1=0,si2=0,si3=0,si4=0;ans=0;
map<ll,ll>s1,s2,s3,s4;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
if(s1[y-x]==0){
s1[y-x]=++si1;
}
if(s2[y+x]==0){
s2[y+x]=++si2;
}
if(s3[x]==0){
s3[x]=++si3;
}
if(s4[y]==0){
s4[y]=++si4;
}
num1[s1[y-x]]++;
num2[s2[y+x]]++;
num3[s3[x]]++;
num4[s4[y]]++;
}
for(int i=1;i<=si1;i++){
if(num1[i]>=2)
ans+=num1[i]*(num1[i]-1);
}
for(int i=1;i<=si2;i++){
if(num2[i]>=2)
ans+=num2[i]*(num2[i]-1);
}
for(int i=1;i<=si3;i++){
if(num3[i]>=2)
ans+=num3[i]*(num3[i]-1);
}
for(int i=1;i<=si4;i++){
if(num4[i]>=2)
ans+=num4[i]*(num4[i]-1);
}
printf("%lld\n",ans);
return 0;
}
int main(){
int t;
scanf("%d",&t);
while(t--) work();
return 0;
}
T2 CF1582A Ntarsis' Set
我们可以发现，
\(a[n]=n\) 时 答案就是\(n*k+1\)
\(a[n]=n+1\) 时设不删除第 \(b\) 小的数，答案就是 \(n*(k-1)+b\)
删除第 \(k\) 小的数相当于让后面不会被删除的数的位置减一，考虑二分答案所在的位置，如果位置减到了零就意味着答案不合法。显然答案是满足单调性的。
点击查看代码
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int n,k,a[200010],ans,an2,ma,top=1;
bool check(int x){
int now=n;
for(int i=1;i<=k;i++){
while(a[now]>x)now--;
x-=now;
}
return x>0;
}
void work(){
//freopen("set_.in","r",stdin);
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
if(a[1]>1){
printf("1\n");
return;
}
int l=1,r=n*k+1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%lld\n",ans);
return;
}
signed main(){
int t;
scanf("%lld",&t);
while(t--) work();
return 0;
}
T3 CF932E Team Work
\[\begin{aligned}
F(n,m)&=\sum\limits_{i=1}^n{n\choose i}i^m\\
&=n\sum\limits_{i=1}^n{n-1\choose i-1}i^{m-1}\\
&=n\left(\sum\limits_{i=1}^n{n\choose i}i^{m-1}-\sum\limits_{i=1}^n{n-1\choose i}i^{m-1}\right)\\
&=n(F(n,m-1)-F(n-1,m-1))
\end{aligned}
\]
边界为 \(f(n, 0) = 2^n - 1\)，复杂度 \(\mathcal{O}(k^2)\)。
除了排列组合这道题也可以使用第二类斯特林数做。
注意如果使用左移操作求 \(2\) 的整数次幂会发生溢出导致答案错误
递推要比记忆化搜索快的多。
记忆化搜索版
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int n,k,ans,jc[200010],fc[200010],inv[200010];
const int mod=1e9+7;
int dp[5010][5010];
int qpow(int x,int y){
int an=1;
while(y){
if(y&1){
an*=x;
an%=mod;
}
x*=x;
x%=mod;
y>>=1;
}
return an;
}
int cc(int x,int y){
if(x<y) return 0;
return jc[x]*fc[y]%mod*fc[x-y]%mod;
}
void work(){
jc[0]=jc[1]=1;
inv[0]=inv[1]=1;
fc[0]=fc[1]=1;
for(long long i=2;i<=200000;i++){
jc[i]=jc[i-1]*i%mod;
inv[i]=((mod-mod/i*inv[mod%i])%mod+mod)%mod;
fc[i]=fc[i-1]*inv[i]%mod;
}
for(int i=1;i<=n;i++){
ans+=cc(n,i)*qpow(i,k)%mod;
ans%=mod;
}
printf("%lld",ans);
return;
}
int dfs(int x,int y){
if(dp[x-(n-k)][y]!=0) return dp[x-(n-k)][y];
if(y==0) return dp[x-(n-k)][y]=qpow(2,x)-1;
return dp[x-(n-k)][y]=x*((dfs(x,y-1)-dfs(x-1,y-1)+mod)%mod)%mod;
}
signed main(){
scanf("%lld%lld",&n,&k);
if(n<k) work();
else printf("%lld",dfs(n,k));
return 0;
}
递推版
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
int n,k,ans,jc[200010],fc[200010],inv[200010];
const int mod=1e9+7;
int dp[5010][5010];
int qpow(int x,int y){
int an=1;
while(y){
if(y&1){
an*=x;
an%=mod;
}
x*=x;
x%=mod;
y>>=1;
}
return an;
}
int cc(int x,int y){
if(x<y) return 0;
return jc[x]*fc[y]%mod*fc[x-y]%mod;
}
void work(){
jc[0]=jc[1]=1;
inv[0]=inv[1]=1;
fc[0]=fc[1]=1;
for(long long i=2;i<=200000;i++){
jc[i]=jc[i-1]*i%mod;
inv[i]=((mod-mod/i*inv[mod%i])%mod+mod)%mod;
fc[i]=fc[i-1]*inv[i]%mod;
}
for(int i=1;i<=n;i++){
ans+=cc(n,i)*qpow(i,k)%mod;
ans%=mod;
}
printf("%lld",ans);
return;
}
void work2(){
for(int i=0;i<=k;i++) dp[i][0]=qpow(2,i+n-k)-1;
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
dp[i][j]=(i+n-k)*(dp[i][j-1]-dp[i-1][j-1]+mod)%mod;
}
}
printf("%lld",dp[k][k]);
}
signed main(){
scanf("%lld%lld",&n,&k);
if(n<k) work();
else work2();
return 0;
}