H
签到题，对于每场比赛排名在 lzr010506 前面且同时在两场比赛出现的的队伍，让他们全部去另一场，看看哪种情况 lzr010506 的排名更高即可。
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 1e5+3;
struct team
{
string name;
int num,time;
}a[maxn],b[maxn];
map<string,int> s;
bool cmp(team &x,team &y)
{
if(x.num==y.num) return x.time<y.time;
return x.num>y.num;
}
void solve()
{
int n; cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].name>>a[i].num>>a[i].time,s[a[i].name]++;
int m; cin>>m;
for(int i=1;i<=m;i++)
cin>>b[i].name>>b[i].num>>b[i].time,s[b[i].name]++;
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+m,cmp);
// cout<<"46"<<endl;
// for(int i=1;i<=n;i++)
// {
// cout<<a[i].name<<" "<<a[i].num<<" "<<a[i].time<<endl;
// }
int rank;
int t=0;
for(int i=1;i<=n;i++)
{
if(a[i].name=="lzr010506")
{
rank=i-t;
break;
}
if(s[a[i].name]>1) t++;
}
t=0;
for(int i=1;i<=m;i++)
{
if(b[i].name=="lzr010506")
{
rank=min(rank,i-t);
break;
}
if(s[b[i].name]>1) t++;
}
cout<<rank<<endl;
return ;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; T=1;
while(T--) solve();
return 0;
}
C
不妨假设现在的数组为 a[6]={0,1,2,3,4,5}，则后缀数组为
s
[
1
]
=
a
1
+
a
2
+
a
3
+
a
4
+
a
5
s[1]=a_1+a_2+a_3+a_4+a_5
s[1]=a1+a2+a3+a4+a5
s
[
2
]
=
a
2
+
a
3
+
a
4
+
a
5
s[2]=a_2+a_3+a_4+a_5
s[2]=a2+a3+a4+a5
s
[
3
]
=
a
3
+
a
4
+
a
5
s[3]=a_3+a_4+a_5
s[3]=a3+a4+a5
s
[
4
]
=
a
4
+
a
5
s[4]=a_4+a_5
s[4]=a4+a5
s
[
5
]
=
a
5
s[5]=a_5
s[5]=a5
可以观察到第 i 个元素对后缀数组和的贡献为 i 次，因此移除的时候减，增加的时候加即可。
- 注意取模涉及到减号时要加上 mod 来防止负数。
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int maxn = 5e5+3;
const int mod = 1e9+7;
int a[maxn],sum[maxn];
void solve()
{
int q; cin>>q;
int t,v;
int cnt=0;
int ans=0;
while(q--)
{
cin>>t>>v;
while(t--)
{
ans=(ans-cnt*a[cnt]%mod+mod)%mod; // 涉及到减号取模时一般都要 +mod 来防止负数
cnt--;
}
a[++cnt]=v;
ans=(ans%mod+cnt*a[cnt]%mod)%mod;
cout<<ans<<endl;
}
return ;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; T=1;
while(T--) solve();
return 0;
}
A
求有多长长为 n 的元素在
[
0
,
2
m
)
[0,2^m)
[0,2m) 的序列满足存在一个非空子序列的 AND 和是1。
观察数据范围可以发现，一定至少有 n 个奇数，从二进制的角度来考虑， AND 和为1，最后一位只能是 1，不妨假设满足条件的序列中有 k 个数在满足条件的子序列中，那么不在子序列中的数就是 n-k 个，对于不在子序列中的数，二进制的最后一位一定是0，剩下的随便填，共
2
(
m
−
1
)
∗
(
n
−
k
)
2^{(m-1)*(n-k)}
2(m−1)∗(n−k) 中情况，而挑出来的这k个数要想满足条件，必须满足前 m-1 位每位至少存在一个 0，这样一共是
(
2
k
−
1
)
(
m
−
1
)
(2^k-1)^{(m-1)}
(2k−1)(m−1)。
综上最后的答案为
C
n
k
∗
2
(
m
−
1
)
∗
(
n
−
k
)
∗
(
2
k
−
1
)
(
m
−
1
)
C_n^k*2^{(m-1)*(n-k)}*(2^k-1)^{(m-1)}
Cnk∗2(m−1)∗(n−k)∗(2k−1)(m−1)，k 从 1 到 n。
由于 q 不一定是质数，因此如果需要求逆元的话不能用费马小定理，用 exgcd。
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;
const int maxn = 5001;
int pw[maxn],C[maxn];
int n,m,mod;
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
void solve()
{
cin>>n>>m>>mod;
pw[0]=1;
int q=max(n,m);
for(int i=1;i<=q;i++)
pw[i]=(pw[i-1]*2)%mod;
C[0]=1;
for(int i=1;i<=n;i++) // 计算 C[n][i];
for(int j=i;j>0;j--)
C[j]=(C[j]+C[j-1])%mod;
int res=0;
for(int k=1;k<=n;k++)
{
int cur1=ksm(pw[m-1],n-k);
int cur2=ksm(pw[k]-1,m-1);
res=(res+(ll)cur1*cur2%mod*C[k]%mod)%mod;
}
cout<<(res+mod)%mod<<endl;
return ;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; T=1;
while(T--) solve();
return 0;
}
B
和第一题背景一样，只不过满足条件的子序列需要大于等于2。
正难则反，采用容斥，用第一问的答案减去满足条件的子序列为 1 的序列个数即可。
下面分析满足条件的子序列为1的序列的性质，假设满足条件的子序列的长度为 k ，即奇数的个数为 k，那么这 k 个数全部化为二进制可以对应出一个 m*k 的数表，每行对应了一个数的二进制，首先最后一列肯定全部为 1。可以发现，要让子序列的情况唯一，那么这 k 个数一定在某一位有一个 0 且这个零在这一列唯一，这样才能保证删除任意一个数都会使异或和不为 1。我们将这样的 0 所在的位置称为特殊位。
显然，一个数可能有多个特殊位，但一个特殊位一定只对应一个数。
设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 为前
i
i
i 个数有
j
j
j 个特殊位，对于第
j
j
j 个特殊位，可以由前
i
−
1
i-1
i−1 行的任何一行承担，剩下的
j
−
1
j-1
j−1 个特殊位有两种情况，一种是由前
i
−
1
i-1
i−1 个数承担，一种是由前
i
i
i 个数承担，从而有转移方程
d
p
[
i
]
[
j
]
=
i
∗
(
d
p
[
i
−
1
]
[
j
−
1
]
+
d
p
[
i
]
[
j
−
1
]
)
dp[i][j]=i*(dp[i-1][j-1]+dp[i][j-1])
dp[i][j]=i∗(dp[i−1][j−1]+dp[i][j−1])。
也可以这么理解，新加进来的特殊位可以被这
i
i
i 个数之一所对应，移除这一位特殊位后肯能还有
i
i
i 个数对应特殊位，也可能有
i
−
1
i-1
i−1 个数对应特殊位。
记这
k
k
k 个二进制最后一位位 1 的数总共对应了
t
t
t 个二进制数，那么
t
t
t 从
k
k
k 到
m
−
1
m-1
m−1 均为要减去的那部分，方案数为
C
n
k
∗
2
(
n
−
k
)
(
m
−
1
)
∗
d
p
[
k
]
[
t
]
∗
(
2
k
−
1
−
t
)
m
−
1
−
t
C_n^k*2^{(n-k)(m-1)}*dp[k][t]*(2^k-1-t)^{m-1-t}
Cnk∗2(n−k)(m−1)∗dp[k][t]∗(2k−1−t)m−1−t ，
t
t
t 从
k
k
k 到
m
−
1
m-1
m−1 求和。其中
C
n
k
∗
2
(
n
−
k
)
(
m
−
1
)
C_n^k*2^{(n-k)(m-1)}
Cnk∗2(n−k)(m−1) 和第一问相同，代表偶数的排列方式，即选出偶数再讨论其前面的
m
−
1
m-1
m−1位
d
p
[
k
]
[
t
]
∗
(
2
k
−
1
−
t
)
m
−
1
−
t
dp[k][t]*(2^k-1-t)^{m-1-t}
dp[k][t]∗(2k−1−t)m−1−t 代表了奇数的排列方案数
d
p
[
k
]
[
t
]
dp[k][t]
dp[k][t] 是除最后一位外的 t 个特殊位对应的特殊列的排列方案，剩下的
m
−
1
−
t
m-1-t
m−1−t 列需要满足 0 的个数大于等于 2，因为为 1 的时候不满组
t
t
t 个特殊位的前提，
t
t
t 为 0 的时候又不满足异或和为 1 的性质。这
m
−
1
−
t
m-1-t
m−1−t 列每一列的方案为
2
k
−
1
−
t
2^k-1-t
2k−1−t ，全部的方案数减去全为 1 的和有一个是 0 的方案。