C - Triangular Relationship
枚举 \(a\bmod k\) 的值，\(b\bmod k,c\bmod k\) 的值也就确定了，算下贡献就好了。
#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
int main()
{
scanf("%d%d",&n,&k);
long long ans=0;
for(int a=0;a<k;a++)
{
int b=(-a+k)%k;
int c=(-a+k)%k;
if((b+c)%k!=0) continue;
int ca=n/k+(a<=n%k),cb=n/k+(b<=n%k),cc=n/k+(c<=n%k);
if(a==0) ca--;
if(b==0) cb--;
if(c==0) cc--;
ans+=1LL*ca*cb*cc;
}
printf("%lld",ans);
return 0;
}
D - All Your Paths are Different Lengths
\(n\le 20\) 容易让人想到二进制拆分。发现可以构造出 \([0,2^{n-1})\) 的方案来，具体的说，我们在 \((i,i+1)\) 中连权值为 \(0,2^{i-1}\) 的两条边。然后考虑 \(L\) 怎么做，将 \(L\) 的每一位分离开来，如果 \(L\) 的第 \(i-1\) 位为 \(0\)，在 \((i,n)\)中连一条权值为将后 \(i\) 位置为 \(0\) 后的 \(L\) 的权值。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<tuple>
using namespace std;
int L;
int n,m;
vector<tuple<int,int,int>>edge;
int main()
{
scanf("%d",&L);
int n=log2(L)+1;
for(int i=1;i<n;i++)
edge.emplace_back(i,i+1,1<<(i-1)),edge.emplace_back(i,i+1,0);
for(int i=1;i<n;i++)
if(L&(1<<(i-1))) edge.emplace_back(i,n,(L>>i)<<i);
int m=edge.size();
printf("%d %d\n",n,m);
for(auto [u,v,w]:edge)
printf("%d %d %d\n",u,v,w);
return 0;
}
E - Stop. Otherwise...
对于每次询问，我们可以将数分成两个部分，一部分是选了当前这个数不能选另一个数，另一部分是选了当前这个数对于其他数没有影响。令 \(f_{i,j}\) 表示考虑前一部分的 \(i\) 种颜色填满 \(j\) 个位置的方案数，\(g_{i,j}\) 表示后一部分的 \(i\) 种颜色（每种颜色如果存在可以换成另一种）填满 \(j\) 个位置的方案数。直接转移是 \(O(n^2m)\) 的，前缀和优化一波就是 \(O(nm)\) 的。每次询问暴力合并一下就好了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2005;
const int MOD=998244353;
int n,m;
int f[N][N],g[N][N];
int sumf[N][N],sumg[N][N];
int pw2[N];
int main()
{
scanf("%d%d",&m,&n);
sumf[0][0]=f[0][0]=1;
for(int j=1;j<=n;j++)
sumf[0][j]=(sumf[0][j-1]+f[0][j])%MOD;
for(int i=1;i<=m;i++)
{
for(int j=0;j<=n;j++)
f[i][j]=f[i-1][j];
for(int j=1;j<=n;j++)
f[i][j]=(f[i][j]+sumf[i-1][j-1])%MOD;
sumf[i][0]=f[i][0];
for(int j=1;j<=n;j++)
sumf[i][j]=(sumf[i][j-1]+f[i][j])%MOD;
}
sumg[0][0]=g[0][0]=1;
for(int j=1;j<=n;j++)
sumg[0][j]=(sumg[0][j-1]+g[0][j])%MOD;
for(int i=1;i<=m;i++)
{
for(int j=0;j<=n;j++)
g[i][j]=g[i-1][j];
for(int j=1;j<=n;j++)
g[i][j]=(g[i][j]+2LL*sumg[i-1][j-1])%MOD;
sumg[i][0]=g[i][0];
for(int j=1;j<=n;j++)
sumg[i][j]=(sumg[i][j-1]+g[i][j])%MOD;
}
for(int i=2;i<=2*m;i++)
if(i%2==0)
{
int cnt1=i>m?i-m-1:m-i+1,cnt2=i>m?m-i/2:(i-1)/2;
int ans=0;
ans=(ans+f[cnt1][n])%MOD;
for(int j=1;j<=n;j++)
ans=(ans+1LL*g[cnt2][j]%MOD*f[cnt1][n-j])%MOD;
ans=(ans+1LL*f[cnt1][n-1])%MOD;
for(int j=1;j<=n-1;j++)
ans=(ans+1LL*g[cnt2][j]%MOD*f[cnt1][n-1-j])%MOD;
printf("%d\n",ans);
}
else
{
int cnt1=i>m?i-m-1:m-i+1,cnt2=i>m?m-i/2:i/2;
int ans=0;
ans=(ans+f[cnt1][n])%MOD;
for(int j=1;j<=n;j++)
ans=(ans+1LL*g[cnt2][j]%MOD*f[cnt1][n-j])%MOD;
printf("%d\n",ans);
}
return 0;
}
Revenge of BBuBBBlesort!
一次操作相当于交换两个距离为 \(1\) 的数，所以如果奇数位置上有偶数，偶数位置上奇数显然是不合法的。
把奇数位和偶数位分成两个排列，一次操作会使得原排列中的逆序对减少 \(3\)，分割后的排列的逆序对减少 \(1\)。
所以可以发现一个必要条件即为原序列的逆序对个数为 \(3\) 的倍数，且为奇数位和偶数位的 \(3\) 倍。
可以证明这也是充分条件。
- 如果交换后原序列的逆序对数减少了 \(3\)，那么这一定是一个合法的操作。
- 考虑对分开后的两个排列冒泡排序，每次这两个排列中的某一个逆序对数会减少 \(3\)。
则可以发现每次操作都是满足第一个条件的，所以只要满足第二个条件就是合法的。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300005;
int n;
int p[N];
struct BIT
{
int C[N];
void clear()
{
memset(C,0,sizeof(C));
return;
}
int lowbit(int x)
{
return x&-x;
}
void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
C[i]+=y;
return;
}
int getsum(int x)
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))
res+=C[i];
return res;
}
int query(int l,int r)
{
return getsum(r)-getsum(l-1);
}
}T;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
for(int i=1;i<=n;i++)
if(p[i]%2!=i%2)
{
printf("No");
return 0;
}
long long cnt=0;
for(int i=1;i<=n;i++)
cnt+=T.query(p[i]+1,n),T.add(p[i],1);
T.clear();
long long cnt1=0;
for(int i=1;i<=n;i+=2)
cnt1+=T.query(p[i]+1,n),T.add(p[i],1);
T.clear();
long long cnt2=0;
for(int i=2;i<=n;i+=2)
cnt2+=T.query(p[i]+1,n),T.add(p[i],1);
if(cnt%3==0&&3*(cnt1+cnt2)==cnt) printf("Yes");
else printf("No");
return 0;
}