上一次写题解也是若干年前的事了。
不过今天的题确实比较好改。
命题
签到题。状压一下看是任意还是存在，从前边两个状态与或者或出来。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,q,dp[21][1<<20];
char s[1<<20];
int main(){
scanf("%d%s%d",&n,s,&q);
for(int i=0;i<(1<<n);i++)dp[0][i]=s[i]-'0';
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<i);j++){
for(int k=0;k<(1<<n-i);k++){
int s=(k<<i)|j;
if((j>>i-1)&1)dp[i][s]=dp[i-1][s]|dp[i-1][s^(1<<i-1)];
else dp[i][s]=dp[i-1][s]&dp[i-1][s^(1<<i-1)];
}
}
}
while(q--){
int x;scanf("%d",&x);
putchar(dp[n][x]+'0');
}
puts("");
return 0;
}
分组
赛时口胡出了 \(O(n^2)\) 的，没写。饥饿。
题解的线性做法看不懂，来个思路不太一样的。
仍然分成两种情况考虑：在 \(a_k\) 之前填满一组和在 \(a_k\) 及以后填满一组。先看第一种。假设我们在 \(a_i\) 前填满一边，那么总数显然 \(2^{a_i}\)，方案呢？我们用总的减掉没填满的方案即可。递推没填满的方案时考虑元素 \(i\) 分到哪一组，再减掉它正好填满的方案。
然后是第二种，即在 \(a_k\) 及以后填满的。这样的话，前面有 \(a_k-k\) 个被分到了两组。此时我们第一组的个数显然不能超过 \(n-k\)。于是枚举第一组的个数减掉不合法的即可。通过这种方式我们成功避免了对后缀和的讨论。
别忘了最后 \(\times 2\)。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int mod=998244353;
int n,q,ans,jc[200010],inv[200010],pw[200010],invpw[200010],s[200010],a[200010];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int C(int n,int m){
if(n<m)return 0;
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
scanf("%d%d",&n,&q);jc[0]=inv[0]=pw[0]=invpw[0]=s[0]=1;
for(int i=1;i<=2*n;i++)jc[i]=1ll*jc[i-1]*i%mod,pw[i]=(pw[i-1]<<1)%mod;
inv[2*n]=qpow(jc[2*n],mod-2);invpw[2*n]=qpow(pw[2*n],mod-2);
for(int i=2*n-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod,invpw[i]=2ll*invpw[i+1]%mod;
for(int i=1;i<=2*n;i++)s[i]=(2ll*s[i-1]-C(i-1,n-1)+mod)%mod;
while(q--){
int k;scanf("%d",&k);ans=0;
for(int i=1;i<=k;i++){
scanf("%d",&a[i]);
ans=(ans+1ll*invpw[a[i]]*(pw[a[i]-i]-s[a[i]-i]+mod))%mod;
}
int ret=s[a[k]-k];
for(int i=n-k+1;i<n;i++)ret=(ret-C(a[k]-k,i)+mod)%mod;
ans=(ans+1ll*ret*invpw[a[k]])%mod;
printf("%d\n",(ans<<1)%mod);
}
return 0;
}
题目
简单题，不知道为啥场上根本没看。
考虑到每个相同的 \(a_i\) 一定是递减的。那么每个 \(a_i\) 可以从前面最后一个 \(a_i-1\) 转移得到，于是偏序关系形成一个 DAG。显然每个位置的答案就是 \(n+1-size_i\)，其中 \(size_i\) 为比 \(i\) 大的个数。
那这个很好统计，我们先倒着扫一遍，先不考虑递减，把转移边的 \(size\) 先累加进来，然后正着扫的时候开个桶记录之前所有 \(a_i\) 的 \(size\) 之和就能解决递减的问题。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int mod=998244353;
int n,lim,seed,ans,a[10000010],pre[10000010],pos[10000010],size[10000010],cnt[10000010];
int __my_rand (int *seed)
{
*seed = *seed * 1103515245 + 12345;
return ((unsigned)*seed) / 34;
}
void gen (int N, int Lim, int seed, int* a)
{
int cur = 0;
for (int i = 1; i <= N; i ++)
{
int rd = __my_rand(&seed);
if (rd % std::min(10, cur + 1) == 0 && cur < Lim) a[i] = ++cur;
else a[i] = (__my_rand(&seed) % cur) + 1;
}
}
int main(){
scanf("%d%d%d",&n,&lim,&seed);
gen(n,lim,seed,a);
for(int i=1;i<=n;i++)pre[i]=pos[a[i]-1],pos[a[i]]=i;
for(int i=n;i>=1;i--)size[i]++,size[pre[i]]+=size[i];
int pw=1;
for(int i=1;i<=n;i++){
cnt[a[i]]+=size[i];
ans=(ans+1ll*pw*(n+1-cnt[a[i]]))%mod;
pw=233ll*pw%mod;
}
printf("%d\n",ans);
return 0;
}