Atcoder 232
Atcoder 232
\(E.\) Rook Path
题意
给定一个\(N\times N\)的网格，在\((X_1,Y_1)\)处有一个机器人，它可以朝上下左右移动，现在它要通过走\(K\)步到达\((X_2,Y_2)\)，每次走的格子不能与当前格子相同，问总共有多少种走法，答案对\(998244353\)取模
\(1\le N,M\le 10^9\) \(1\le K \le 10^6\)
Sol
定义\(f1[i][0]\)表示用了\(i\)步走行没到目标行\(X_2\)的方法数，\(f1[i][1]\)表示用了\(i\)步走行到了目标行\(X_2\)的方法数
? \(f2[i][0]\)表示用了\(i\)步走列没到目标列\(Y_2\)的方法数，\(f2[i][1]\)表示用了\(i\)步走列到了目标列\(Y_2\)的方法数
那么最后的答案就是对于每个\(i\)（\(0\le i\le K\)），对答案的贡献为\(f1[i][1]*f2[k-i][1]*C_k^i\)，最后乘\(C_k^i\)是因为\(k\)步中选择\(i\)步走行
具体转移，以\(f1\)为例
\(f1[i][1]=f1[i][1]+f1[i-1][0]\) 如果用了第\(i\)步走到目标行，那么答案贡献加上用了第\(i-1\)没有走到目标行，并且由于第\(i-1\)步的下一步一定到达目标行，所以第\(i\)步的走法位移，可以看做\(f1[i-1][0]*1\)
\(f[i][0]+=f[i-1][1]*(N-1)+f[i-1][0]*(N-2)\) 如果用了第\(i\)步没有走到目标行，那么可以由用了第\(i-1\)步走到目标行和没有走到目标行转移过来，如果用了第\(i-1\)步走到目标行，那么用了第\(i\)步由于没有走到目标行，那么除了目标行可能落在任何的行就有\((N-1)\)个情况；如果用了第\(i-1\)步没有走到目标行，由于第\(i\)步是用来走行的，并且题目要求不能原地踏步，所以第\(i\)步走的行一定不会是当前行，又由于第\(i\)步没有走到目标行，所以有\(N-2\)中选择。
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=1e6+10;
int fac[N];
ll f1[N][2],f2[N][2];
ll qmi(int x,int y)
{
ll res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
int C(int n,int m)
{
return fac[n]*qmi(fac[m],mod-2)%mod*qmi(fac[n-m],mod-2)%mod;
}
int main()
{
int n,m,k;
int x1,x2,y1,y2;
rd(n),rd(m),rd(k);
rd(x1),rd(y1),rd(x2),rd(y2);
fac[0]=1;
for(int i=1;i<=k;i++) fac[i]=1ll*fac[i-1]*i%mod;
if(x1!=x2) f1[0][0]=1;
else f1[0][1]=1;
if(y1!=y2) f2[0][0]=1;
else f2[0][1]=1;
for(int i=1;i<=k;i++)
{
f1[i][1]=(f1[i][1]+f1[i-1][0])%mod;
f1[i][0]=(f1[i][0]+f1[i-1][1]*(n-1)%mod+f1[i-1][0]*(n-2)%mod)%mod;
f2[i][1]=(f2[i][1]+f2[i-1][0])%mod;
f2[i][0]=(f2[i][0]+f2[i-1][1]*(m-1)%mod+f2[i-1][0]*(m-2)%mod)%mod;
}
int ans=0;
for(int i=0;i<=k;i++)
{
ll res=f1[i][1]*f2[k-i][1]%mod;
ans=(ans+res*C(k,i)%mod)%mod;
}
cout< \(F.\)Simple Operations on Sequence
题意
给定两个长度为\(N\)的序列\(A=(A_1,A_2,...,A_N)\)和\(B=(B_1,B_2,...,B_N)\)
可以对\(A\)进行以下两种操作:
1.将\(A_i\)加1或减1，消耗\(X\)点体力。
2.交换\(A_i\)和\(A_{i+1}\)，消耗\(Y\)点体力。\((1\le i\le N-1)\)
问最后将\(A\)变为\(B\)最少需要消耗多少体力。
Sol
首先最后的代价是由加减多少和交换次数决定的。
可以发现，先交换再加减和先加减再交换是可以做到等价的。
于是我们可以先交换，再加减。
记经过若干次交换后的\((A_1,A_2,...,A_n)\)为\((A_{p_1},A_{p_2},...,A_{P_n})\)
- 交换的代价就是\(P=(P_1,P_2,...,P_n)\)中逆序对的数量\(inv(P)\)*\(Y\)
- 加减的代价就是就是\(\sum_{i=1}^n|A_{p_i}-B_i|*X\)
那么最后的答案就是最小化\(\sum_{i=1}^n|A_{P_i}-B_i|*X+inv(P)*Y\)
\(\sum_{i=1}^n|A_{P_i}-B_i|*X+inv(P)*Y\)
=\(\sum_{i=1}^n|A_{P_i}-B_i|*X+(\sum_{i=1}^n\{j:j>i,P_j\lt P_i\})*Y\)
=\(\sum(|A_{P_i}-B_i|*X+\{j:j>i,P_j\lt P_i\}*Y)\)
=\(\sum_{i=1}^n(|A_{P_i}-B_i|*X+\{p:p\in s?\{P_1,P_2,...,P_{i-1}\},p\lt P_i\}*Y)\)
因此考虑状态压缩\(dp[S]\)其中\(S\)是表示\(P=(P_1,P_2,...,P_i)\)集合的一个二进制数，表示已经完成\(B\)的前\(i\)个，对应的\((B_1,B_2,...,B_i)\)是由\((A_{P_1},A_{P_2},...,A_{P_i})\)加减的到，前面已经交换过了。
那么当转移一个状态\(S\)时，假设这个状态\(S\)已经确定的\(B\)的个数为\(cnt\)
那么在更新第\(B_{cnt+1}\)时，首先在\(S\)中存在的下标\(A_i\)不能选，然后枚举还没选的\(A\)，看一下哪一个\(A_j\)操作到\(B_{cnt+1}\)消化最少,加减的代价是\(|A_j-B_{cnt+1}|*X\)，交换的代价是不在\(S\)中小于\(j\)的个数。因为这个\(j\)肯定比后面还没放的\(x\)下标要靠前，那么找比\(j\)小的说明剩下小的下标\(x\)就是放在\(j\)后面，这样就找到了一组逆序对。
#include
#define ll long long
#define inf 1e18
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=20;
ll dp[1<<20];
int n;
ll A[N],B[N];
ll X,Y;
int nixu(int s,int x)
{
int cnt=0;
for(int i=1;i<=n;i++)
if(!(s&(1<<(i-1)))&&i \(G.\) Modulo Shortest Path
题意
现在有一个\(N\)个点的完全图，每个点有两个权值\(A_i\)和\(B_i\)，从点\(i\)到\(j\)的权值为\((A_i+B_j)mod\ M\)，现在要你求一条从\(1\)到\(N\)的权值最小的路径
\(2\le N \le 2\times 10^5\) \(2\le M \le 10^9\) \(0\le A_i,B_i \le M\)
Sol
建图方式(为什么这样我太菜了不会证明)
- 首先建立一个\(0\)号点，每个点\(i\)向\(0\)号点连边权为\(A_i\)的有向边，\(0\)号点向\(i\)连边权为\(B_i\)的有向边
- 将每个\(A_i，M-B_i\)去重离散排序从\(N+1\)开始编号，
- 然后将这些新编号后的点按从小到大的顺序两两连一条有向边，边权为没；离散化后大的减去小的。
- 再将每个点\(i\)向\(id[A_i]\)连一条边权为0的有向边，将\(id[M-B_i]\)向\(i\)连一条边权为0的有向边
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define Mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=2e5+10;
int n,mod;
int A[N],B[N];
vector>e[4*N];
vectorv;
mapid;
ll dis[N*4];
int vis[N*4];
void init()
{
mapid;
vectorv;
for(int i=1;i<=n;i++) v.pb(A[i]),v.pb(B[i]);
sort(v.begin(),v.end());
int k=n+1;
id[v[0]]=k;
for(int i=1;i,vector>,greater>>q;
q.push({0,1});
while(q.size())
{
auto t=q.top();
q.pop();
if(vis[t.se]) continue;
vis[t.se]=1;
for(auto ti:e[t.se])
{
int v=ti.fi;ll w=ti.se;
if(dis[v]>dis[t.se]+w&&!vis[v])
{
dis[v]=dis[t.se]+w;
q.push({dis[v],v});
}
}
}
cout< \(H.\) King's Tour
题意
给定一个\(H\times W\)的网格，给定一个点\((a,b)\)，让你构造一条从\((1,1)\)到\((a,b)\)的一条将每个网格都经过一次且最后到达终点的路径。（曼哈顿回路）
Sol
递归构造（以下图片均来自ATcoder官方题解)
- 如果\(H=2\)，那么走法是唯一的
假设旗子在\((a,b)\)
那么唯一的路径就是\((1,1)->(2,1)->(1,2)->...->(1,b-1)->(2,b-1)->(3-a,b)->(3-a,b+1)->...->(3-a,W)\\->(a,W)->(a,W-1)->...->(a,b+1)->(a,b)\)
-
如果\(H>2，W=2\) 那么反转网格又变成\(H=2\)
-
如果\(H>2\)和\(W>2\)
- 如果\((a,b)\)不在\(S\)中，那么可以先沿上面的方法走，走到\((H,2)\)后继续把整个图上下反转，并且删去第一行得到一个子网格，然后就又是从第一个开始走，递归
- 如果\((a,b)\)在\(S\)中，那么同样旋转整个方格，交换行和列，总可以使得旗子不在\(S\)中。
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
using pii=pair;
vector solve(int h,int w,int a,int b)
{
vectorres;
if(h==2)
{
for(int i=1;i=b+1;i--) res.pb({2,i});
res.pb({a,b});
}
else if(h>2&&w==2||b==1|| a==h&&b==2 )
{
res=solve(w,h,b,a);
for(auto &t:res) swap(t.fi,t.se);
}
else
{
for(int i=1;i<=h;i++) res.pb({i,1});
auto res1=solve(h,w-1,h+1-a,b-1); //走到(h,2)后上下反转
for(auto &t:res1) t.fi=h+1-t.fi,t.se++;
res.insert(res.end(),res1.begin(),res1.end());
}
return res;
}
int main()
{
int h,w,a,b;
rd(h),rd(w),rd(a),rd(b);
auto ans=solve(h,w,a,b);
for(auto p:ans) cout<