T1 构造题
没啥好说的，大样例一眼出规律
#include<bits/stdc++.h>
#define N 310
using namespace std;
int n,l[N][N],r[N][N],a[N][N];
int main(){
freopen("squ.in","r",stdin);
freopen("squ.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
if(n%2==1){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++)
cout<<(i+j-2)%n+1<<" ";
cout<<"\n";
}
}else if(n==2) cout<<"-1";
else{
for(int i = 1;i<=n;i++)
a[1][i] = i;
swap(a[1][n],a[1][n-1]);
for(int i = 1;i<n/2;i++)
a[n][i] = i*2;
for(int i = 1;n/2+i-1<n;i++)
a[n][n/2+i-1] = 2*i-1;
a[n][n] = n;
for(int i = 2;i<n;i++)
for(int j = 1;j<n;j++)
a[i][j] = (i+j-2)%(n-1)+1;
for(int i = 2;i<n;i++){
a[i][n] = a[i][i-1];
a[i][i-1] = n;
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<"\n";
}
}
return 0;
}
T2 括号串
首先我们可以发现规律
一个 \(1\) 操作就是将答案加当前层的括号个数（包括添加的这个）
一个 \(2\) 操作就是将答案加一并加一层，新的一层只有添加的这个
对于 \(3\) 操作而言就是删掉或恢复一个括号或者是减去或恢复一层
对于被减去的一层，我们就需要将剩下的括号添加到它的上一层去，被恢复的则相反
但是暴力实现肯定不行的，需要用数据结构来维护
我们可以发现，其实修改只有单点修改，我们需要的只是当前层的左右端点，查询就是整个的答案
那么用线段树就可以快捷的实现了
不得不说，题解中的线段树实现得挺巧妙的
#include<bits/stdc++.h>
#define N 200010
#define int long long
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
struct node{
int ltot,rtot,tot,flag;
}t[N<<2];
int n,opt[N],pos[N];
bool vis[N];
node pushup(node x,node y){
node ans;
ans.ltot = (x.flag?x.ltot:x.ltot+y.ltot);
ans.rtot = (y.flag?y.rtot:x.rtot+y.rtot);
ans.tot = x.tot+y.tot+x.rtot*y.ltot;
ans.flag = x.flag|y.flag;
return ans;
}
void change(int p,int l,int r,int pos){
if(l==r){
if(vis[l]) t[p].tot = t[p].ltot = t[p].rtot = t[p].flag = 0;
else{
if(opt[l]==1)
t[p].tot = t[p].ltot = t[p].rtot = 1,t[p].flag = 0;
else t[p].tot = t[p].rtot = t[p].flag = 1,t[p].ltot = 0;
}
return ;
}
int mid = (l+r)>>1;
if(pos<=mid) change(lc,l,mid,pos);
else change(rc,mid+1,r,pos);
t[p] = pushup(t[lc],t[rc]);
}
signed main(){
freopen("str.in","r",stdin);
freopen("str.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
opt[0] = 1;change(1,0,n,0);
for(int i = 1;i<=n;i++){
cin>>opt[i];
switch(opt[i]){
case 1:
case 2:{
pos[i] = i;
break;
}
case 3:{
cin>>pos[i];
pos[i] = pos[pos[i]];
break;
}
}
change(1,0,n,pos[i]);
vis[pos[i]]^=1;
cout<<t[1].tot<<"\n";
}
return 0;
}
T3 博弈
考虑枚举哪一张卡片使得游戏结束，以及这张卡片在哪一行，设这是第 \(k\) 张卡片，且在第 \(i\) 行
那么这一行之外的部分对于分数是不重要的，考虑计算这种情况出现的概率，则需要满足如下要求：
- 在放这张卡片之前，这一行只剩一个空位
- 其它行没有满
那么可以做一个 \(d p: f_{i, j}\) 表示考虑了前 \(i\) 行，前 \(i\) 行中一共放了 \(j\) 张卡片的概率，枚举结束的行做 \(m\) 次这样的 \(d p\) ，复杂度为 \(\mathcal O\left((n+m)^{2} m\right)\)
这样可以得到 \(p_{i, j}\) 表示放了 \(i\) 张卡片后结束，且在第 \(j\) 行结束的概率
然后考虑计算分数的贡献，此时最后一张卡片一定在这一行，其它卡片出现的概率相等且这一行内的可能的顺序出现的概率都相等
设 \(k\) 为使游戏结束的卡片的编号，因为其它卡片出现的概率相同，可以看成在前面选 \(l_{i}-1\) 张卡片和第 \(k\) 张卡片以任意顺序排列作为分数，然后除以 \(C_{k-1}^{l_{i}-1} * l_{i}\) !
考虑期望线性性，一张卡片的贡献为它的值乘上 \(10^{s}\) ，其中 \(s\) 为这张卡片后面的卡片的字符串长度和
因为第 \(k\) 张卡片需要特殊考虑，所以计算第 \(x\) 张卡片的贡献时，考虑枚举它在这一行的 \(j\) 个位置，以及第 \(k\) 张卡片在它的哪一侧
考虑第 \(k\) 张卡片在它的左侧的情况，此时相当于在前 \(k-1\) 张卡片除去自己中选出 \(l_{i}-j\) 张放在它右侧，设 \(s^{\prime}\) 为这些卡片的字符串长度和，那么一种方案的贡献为 \(10^{s^{\prime}}\)
设 \(s^{\prime \prime}\) 为这张卡片字符串长度，那么相当于选一个放在右侧会有 \(10^{s^{\prime \prime}}\) 的贡献，所有贡献相乘
那么可以使用一个 \(d p\) 计算这个贡献。第 \(k\) 张卡片在它右侧的情况类似
因此直接的做法相当于枚举 \(x\) ，然后做 \(d p_{s, t}\) 表示考虑 \([1, s]\) 中除去第 \(x\) 张卡片，这部分选了 \(t\) 张卡片的所有方案的贡献和，最后枚举 \(j\) 算贡献，这样的复杂度看起来是 \(\mathcal O\left(n^{5}\right)\) ，但因为 \(\sum l_{i}\) 只有 \(n+m\) ，因此复杂度为 \(\mathcal O\left(n^{3}(n+m)\right)\)
注意到对于不同的 \(x\) ，要求的都是 \(d p_{k-1}\) ，只是不能选的位置不同，可以发现，先求出所有位置都能选时的 \(d p_{k-1}\) ，在要求不能选 \(x\) 时，在 \(d p\) 上做加入物品 \(x\) 时的逆操作即可得到这个值
一种简单的解释方式是，将 \(\mathrm{dp}\) 的第二维看成生成函数，则加入一个物品相当于乘上 \(1+10^{s} x\) ，那么删去这个物品相当于除去这个一次式，可以直接 \(\mathcal O(n)\) 除
时间复杂度 \(\mathcal O\left(n^{2}(n+m)\right)\)
代码实现挺恶心的
#include<bits/stdc++.h>
#define N 310
#define mod ((int)1e9+9)
#define int long long
using namespace std;
int n,m,l[N],fac[N<<1],inv[N<<1],pw[N],val[N],f[N][N],g[N][N][2],g2[N][N][2];
char s[N][N];
int ksm(int x,int y){
int res = 1;
while(y){
if(y&1) res = res*x%mod;
x = x*x%mod;
y>>=1;
}
return res;
}
inline int C(int x,int y){
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int sum = 0;
for(int i = 0;i<m;i++){
cin>>l[i];
sum+=l[i];
}
for(int i = 0;i<n;i++){
cin>>s[i];
int x = strlen(s[i]);
pw[i] = 1;
for(int j = 0;j<x;j++){
pw[i] = pw[i]*10%mod;
val[i] = (val[i]*10+(s[i][j]-'0'))%mod;
}
}
fac[0] = 1;
for(int i = 1;i<=600;i++)
fac[i] = fac[i-1]*i%mod;
inv[600] = ksm(fac[600],mod-2);
for(int i = 599;i>=0;i--)
inv[i] = inv[i+1]*(i+1)%mod;
int ans = 0;
for(int i = 0;i<m;i++){
memset(f,0,sizeof(f));
f[0][0] = 1;
for(int j = 0;j<m;j++)
for(int k = 0;k<=n;k++)
if(f[j][k])
for(int z = l[i]*(i==j);z<=l[j]-(i!=j)&&k+z<=n;z++)
f[j+1][k+z] = (f[j+1][k+z]+f[j][k]*C(l[j],z)%mod)%mod;
for(int k = 0;k<=l[i];k++)
memset(g[k],0,sizeof(g[k]));
g[0][0][0] = 1;
for(int j = 0;j<=sum;j++){
if(j>=l[i]&&j<=n&&j<=sum)
for(int k = 0;k<l[i];k++){
int ways = fac[j-l[i]]*fac[k]%mod*fac[l[i]-k-1]%mod;
ways = inv[sum]*fac[sum-j]%mod*ways%mod;
ans = (ans+f[m][j]*(g[k][l[i]-k-1][1]+mod-g2[k][l[i]-k-1][1])%mod*ways)%mod;
}
for(int k = 0;k<=l[i];k++)
memcpy(g2[k],g[k],sizeof(g2[k]));
for(int k1 = l[i]-1;k1>=0;k1--)
for(int k2 = l[i]-k1;k2>=0;k2--){
int *tmp = g[k1][k2];
if(g[k1][k2][1]){
g[k1+1][k2][1] = (g[k1+1][k2][1]+tmp[1])%mod;
g[k1][k2+1][1] = (g[k1][k2+1][1]+(pw[j]*tmp[1])%mod)%mod;
}
if(g[k1][k2][0]){
g[k1+1][k2][0] = (g[k1+1][k2][0]+tmp[0])%mod;
g[k1][k2+1][0] = (g[k1][k2+1][0]+pw[j]*tmp[0]%mod)%mod;
g[k1][k2][1] = (g[k1][k2][1]+val[j]*tmp[0]%mod)%mod;
}
}
}
}
cout<<ans;
return 0;
}