C 题可不可以算给 Beginner 打开了数数的大门啊。
定义状态 \(f_{i,j}\) 表示长度为 \(i\) 的符合题目要求的数字，结尾数位是 \(j\) 的有多少个。那么递推式就是：
然后就可以数数了。
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=998244353;int n;ll f[1000005][11];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=9;i++)f[1][i]=1; for(int j=2;j<=n;j++){ for(int i=1;i<=9;i++)f[j][i]=(f[j-1][i-1]+f[j-1][i]+f[j-1][i+1])%mod; } cout<<accumulate(f[n]+1,f[n]+10,0ll)%mod; return 0;}很有趣味！
首先可以看出一个字符执行了 \(t\) 次操作以后的长度是好计算的，所以我们先把问题变成一个字符执行 \(t\) 次操作之后的第 \(k\) 个是什么。
上面的东西可以递归处理，定义函数 \(f(c,t,k)\) 表示字符 \(c\) 执行了 \(t\) 次操作得到的字符串的第 \(k\) 个是什么，只是有一个问题：\(t\) 太大了。
观察到每次操作会把字符串长度加倍，所以执行很少操作后，就变成了对 \(f(c,t,1)\) 求值。然而操作三次以后第一个字符等价于没有改变，所以可以直接得到结果。
#include<bits/stdc++.h>using namespace std;typedef long long ll;int n,q;char s[100005];void deal(int c,ll t,ll k){ if(t==0){ cout<<char(c+'A')<<'\n'; return; } if(1ll<<t-1>=k)deal((c+1)%3,t-1,k); else deal((c+2)%3,t-1,k-(1ll<<t-1));}int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>s+1; n=strlen(s+1); cin>>q; while(q--){ ll t,k; cin>>t>>k; ll lgk=1; while(1ll<<lgk<k)lgk++; if(t>lgk){ t-=(t-lgk)/3*3; } for(int i=1;;i++){ if(k>1ll<<t)k-=1ll<<t; else{ deal(s[i]-'A',t,k); break; } } } return 0;}这个题目的标题是怎么回事啊。
我们可以枚举两个字符串相同的前缀有多长，然后在后一个位置给串 \(X\) 填更小的字符，再之后的位置可以随便填了。
特殊地，需要判断 \(X\) 的前半段全部和 \(S\) 相同时，后半段是否小于等于 \(S\)。
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=998244353;const int N=1e6;int n,pw[N+5];char s[N+5];void mian(){ cin>>n>>s+1; int ans=0; bool any=1; for(int i=1;i<=(n+1)/2;i++){ int a=s[i]-'A',b=s[n+1-i]-'A'; ans=(ans+(ll)a*pw[(n+1)/2-i])%mod; any&=a<=b; any|=a<b; } cout<<(ans+any)%mod<<'\n';}int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); pw[0]=1; for(int i=1;i<=N;i++)pw[i]=pw[i-1]*26ll%mod; int T; cin>>T; while(T--)mian(); return 0;}题目标题让我想起了一个叫 black_white_tony 的人。
首先可以考虑把 \(R\) 行 \(C\) 列分配给黑棋，\(P\) 行 \(Q\) 列分配给白棋的方案数，显然是 \(\binom N R \binom M C \binom {N-R} P \binom {M-C} Q\)。
然后我们考虑在 \(R\) 行 \(C\) 列里填入 \(N\) 个棋子，允许有空着的行或者空着的列的方案数，是 \(\binom {R C} N\)。
当然，上面的枚举分配给黑白棋子的行列要求不能有空着的行列，那么我们可以尝试从 \(\binom {R C} N\) 里去掉存在空着的行或者列的方案数。
记录没有空着的行列的方案数为 \(f(R,C,N)\)。
思路是从允许空着的方案数里面减去强制一些行和列空着，然后给剩下的行列放入 \(N\) 个的方案数。
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=998244353;const int precLen=2500;ll qpow(ll a,ll n){ ll res=1; while(n){ if(n&1)res=res*a%mod; a=a*a%mod; n>>=1; } return res;}int fact[precLen+5],inv[precLen+5];ll binom(int n,int r){ if(n<r||r<0)return 0; return (ll)fact[n]*inv[n-r]%mod*inv[r]%mod;}void initialization(){ fact[0]=1; for(int i=1;i<=precLen;i++){ fact[i]=(ll)fact[i-1]*i%mod; } inv[precLen]=qpow(fact[precLen],mod-2); for(int i=precLen-1;i>=0;i--){ inv[i]=(ll)inv[i+1]*(i+1)%mod; }}ll mem[55][55][2505];ll put(int r,int c,int n){ if(r*c<n||max(r,c)>n)return 0; ll &res=mem[r][c][n]; if(res)return res; res=binom(r*c,n); for(int i=1;i<=r;i++)for(int j=n/i;j<=c;j++)if(i!=r||j!=c){ res=(res-binom(r,i)*binom(c,j)%mod*put(i,j,n)%mod+mod)%mod; } return res;}int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); initialization(); int n,m,b,w; cin>>n>>m>>b>>w; ll ans=0; for(int i=1;i<n;i++)for(int j=1;j<m;j++){ ll coef1=binom(n,i)*binom(m,j)%mod*put(i,j,b)%mod; for(int k=1;i+k<=n;k++)for(int l=1;j+l<=m;l++){ ll coef2=binom(n-i,k)%mod*binom(m-j,l)%mod*put(k,l,w)%mod; ans=(ans+coef1*coef2)%mod; } } cout<<ans<<'\n'; return 0;}莫队很厉害！
把询问 \((l,r)\) 离线下来，按照 \((l/\sqrt N,r)\) 升序排序，然后从前往后枚举排序好的询问区间，并且维护实际计算入的区间的左右端点、每个值有出现多少次和答案。在考虑一个新的询问区间时，移动左右端点，就可以计算出答案。
由于右端点一直上升，只有 \(O(\sqrt N)\) 次会从大变小，所以右端点移动次数是 \(O(N \sqrt N)\) 的。
左端点一直在 \(\sqrt N\) 的块内移动，只有 \(O(\sqrt N)\) 次会从一个块走到另一个，所以移动次数也是 \(O(N \sqrt N)\) 的。
移动左右端点，其实就是把当前考虑的值的集合加入或删除一个。维护每个值的出现次数，在增加到偶数时给答案加一，减少到奇数时给答案减一即可。
#include<bits/stdc++.h>using namespace std;const int B=316;int n,q,a[100005],c[100005],res,ans[1000005];pair<pair<int,int>,int> qs[1000005];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cin>>q; for(int i=1;i<=q;i++){ cin>>qs[i].first.first>>qs[i].first.second; qs[i].second=i; } sort(qs+1,qs+1+q,[&](const pair<pair<int,int>,int>& a,const pair<pair<int,int>,int>& b){ if(a.first.first/B!=b.first.first/B)return a.first.first/B<b.first.first/B; if(a.first.second!=b.first.second)return a.first.second<b.first.second; return a.second<b.second; }); int l=1,r=0; for(int i=1;i<=q;i++){ int ql,qr; tie(ql,qr)=qs[i].first; while(r<qr){ ++r; res+=c[a[r]]&1; ++c[a[r]]; } while(l>ql){ --l; res+=c[a[l]]&1; ++c[a[l]]; } while(r>qr){ --c[a[r]]; res-=c[a[r]]&1; --r; } while(l<ql){ --c[a[l]]; res-=c[a[l]]&1; ++l; } ans[qs[i].second]=res; } for(int i=1;i<=q;i++)cout<<ans[i]<<'\n'; return 0;}赛场上不会 Min-Max 容斥也不会 EGF 推算的我真的好蠢啊。
给定一个随机元素的集合 \(S\)，每个元素都有一个随机取值 \(x\)。那么记最小值的期望值为 \(Min(S)\)，最大值的期望值为 \(Max(S)\)，有结论：
也能理解成一组集合中每个元素都有一个单位时间被选中的概率，\(Min(S)\) 为至少选中一个的期望时间，\(Max(S)\) 为全部选完的期望时间。
那么我们在本题中，可以求出每种位置集合，当中至少一个位置被选中的期望时间，就可以用 Min-Max 容斥变成所有位置都被选中的期望时间了。
我们可以 \(f_{i,j,k}\) 表示确定了前 \(i\) 个位置选或者不选，第 \(i\) 个一定选，没有覆盖选了的位置的线段有 \(j\) 个，选的位置的个数的奇偶性是 \(k\) 的方案数。现在就可以枚举上一个选择的位置是什么，然后转移。最后使用虚拟状态 \(f_{n+1,i,0/1}\) 计算答案。
#include<bits/stdc++.h>#include<atcoder/modint>using namespace std;typedef long long ll;typedef atcoder::modint998244353 mint;mint qpow(mint a,ll n){ mint res=1; while(n){ if(n&1)res*=a; a*=a; n>>=1; } return res;}int n,m,sum[405][405];mint f[405][405][2];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=m;i++){ int l,r; cin>>l>>r; sum[l][r]++; } for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)sum[i][j]+=sum[i][j-1]; f[0][0][1]=1; for(int i=1;i<=n+1;i++){ int s=0; for(int j=i-1;j>=0;j--){ s+=sum[j+1][i-1]; for(int k=s;k<=m;k++){ for(int pa=0;pa<2;pa++){ f[i][k][pa]+=f[j][k-s][pa^1]; } } } } mint ans; for(int i=0;i<m;i++){ ans+=f[n+1][i][1]*m/(m-i); ans-=f[n+1][i][0]*m/(m-i); } cout<<ans.val()<<'\n'; return 0;}