摘要
/ | A | B | C | D | E | F | G | H | I | J | K |
---|---|---|---|---|---|---|---|---|---|---|---|
场上 | ✔ | ✔ | ✔ | ||||||||
zyj | ✔ | ✔ | |||||||||
wrf | ✔ | ✔ | |||||||||
lmj | ✔ | ✔ | ✔ | ✔ | ✔ |
题目
A.B-Suffix Array
wrf (赛后)
题意
定义一个函数 $B:char[n] \rightarrow vector[n]$,其含义为:对于原串的第 $i$ 个字符,找到它之前与它相同的字符位置 $j$,结果的第 $i$ 个元素即为 $i-j$。如果不存在这样的字符,相应的结果为 $0$。
举例:
$B(aaa)=(0,1,1)$
$B(abaababb)=(0,1,2,1,3,2,2,1)$
题目要求对给出的,字符集仅为 $\{a,b\}$ 的串的所有后缀做函数 $B$,把结果按字典序排序,输出最后的顺序。
保证串长不超过 $10^5$。
题解
做法
对于字符串的第 $i$ 个字符,定义对偶函数 $b'(i)$,其含义为:对于原串的第 $i$ 个字符,找到它之后与它相同的字符位置 $j$,结果的第 $i$ 个元素即为 $j-i$。如果不存在这样的字符,相应的结果为 $\infty$。
就像题中的函数 $B$,一个字符串的函数 $B'$ 就是由每个位置的 $b'$组成。
定义 $B'$ 上的小于关系为字典序从大到小,并且前缀优先。
举例:
$B'(a)=(\infty)<B'(ab)=(\infty,\infty)<B'(aba)=(2,\infty,\infty)$
按照对偶函数的顺序构造后缀数组即可。
举例:
以串abaabaaaabba
为例:
$rank[i]$ $i$ $s[i:n]$ $B(s[i:n])$ $LCP[i]$ $B'(s[i:n])$ $LCP[B'(i)]$ $1$ $12$ a $0$ $-1$ $\infty$ $-1$ $2$ $11$ ba $0,0$ $1$ $\infty,\infty$ $1$ $3$ $5$ baaaabba $0,0,1,1,1,5,1,3$ $2$ $5,1,1,1,3,1,\infty,\infty$ $0$ $4$ $9$ abba $0,0,1,3$ $3$ $3,1,\infty,\infty$ $0$ $5$ $2$ baabaaaabba $0,0,1,3,2,1,1,1,5,1,3$ $4$ $3,1,2,5,1,1,1,3,1,\infty,\infty$ $2$ $6$ $4$ abaaaabba $0,0,2,1,1,1,5,1,3$ $2$ $2,5,1,1,1,3,1,\infty,\infty$ $0$ $7$ $1$ abaabaaaabba $0,0,2,1,3,2,1,1,1,5,1,3$ $4$ $2,3,1,2,5,1,1,1,3,1,\infty,\infty$ $1$ $8$ $10$ bba $0,1,0$ $1$ $1,\infty,\infty$ $0$ $9$ $8$ aabba $0,1,0,1,3$ $3$ $1,3,1,\infty,\infty$ $1$ $10$ $3$ aabaaaabba $0,1,0,2,1,1,1,5,1,3$ $3$ $1,2,5,1,1,1,3,1,\infty,\infty$ $1$ $11$ $7$ aaabba $0,1,1,0,1,3$ $2$ $1,1,3,1,\infty,\infty$ $1$ $12$ $6$ aaaabba $0,1,1,1,0,1,3$ $3$ $1,1,1,3,1,\infty,\infty$ $2$ 答案即为列 $i$。
证明
详细证明见论文 Parameterized Suffix Arrays for Binary Strings。以下大致描述该论文的思路。
我们只需证明,$B$ 与 $B'$ 存在对应的偏序关系。即
$$ \begin{aligned} B'(s[i:n])<B'(s[j:n]) \Rightarrow B(s[i:n])<B(s[j:n]) \\ B'(s[i:n])=B'(s[j:n]) \Rightarrow B(s[i:n])=B(s[j:n]) \end{aligned} $$
那么 $B'(s[i:n])=B'(s[j:n])$ 时显然。下面考虑小于的情况。
- 如果 $B'(s[i:n])$ 是 $B'(s[j:n])$ 的前缀,那么 $s[i:n]$ 要么是 $s[j:n]$ 的前缀,要么把所有 $s[i:n]$ 中的 $a,b$ 互相代换之后是 $s[j:n]$ 的前缀。反之亦然。
证明:
反证。不妨设 $s_i[k]=s[i+k]=s[n],s_j[k]=s[j+k] \not = s[n]$
那么 $b'_i(k),b'_i(b'_i(k)),\dots$ 中必然有一个为 $n$,$b'_j(k),b'_j(b'_j(k)),\dots$ 中必然没有 $n$。
与 「$B'(s[i:n])$ 是 $B'(s[j:n])$ 的前缀」相矛盾。
另一侧的证明显然。
由此,显然对于任意的 $k$,要么 $b_i(k)=b_j(k)$,要么 $b_i(k)=0$。即 $B(s[i:n])$ 要么是 $B(s[j:n])$ 的前缀,要么存在 $b_i(k)=0<b'_j(k)$。
如果 $B'(s[i:n])$ 不是 $B'(s[j:n])$ 的前缀。那么必然存在 $s[i+k] \not = s[j+k]$。
记满足 $s[i]=s[i+1]= \cdots =s[i+k-1] \not = s[i+k]$ 的串为 $a(k)b$,满足 $s[i]=s[i+1]= \cdots =s[i+k-1]=s[i+k]=s[n]$ 的串为 $a(k)x$。
存在如下没有前缀关系的情况(以下假设 $i<j$):- $a(i)b$ 与 $a(j)b$
pos 1 2 $\cdots$ i-1 i i+1 $B(a(i)b)$ 0 1 $\cdots$ 1 1 0 $B(a(j)b)$ 0 1 $\cdots$ 1 1 1 $B'(a(i)b)$ 1 1 $\cdots$ 1 sth>1 or $\infty$ sth $B'(a(j)b)$ 1 1 $\cdots$ 1 1 1 or sth 可知 $B(a(i)b)<B(a(j)b),B'(a(i)b)<B'(a(j)b)$
- $a(i)b$ 与 $a(j)x$
pos 1 2 ... i-1 i i+1 $B(a(i)b)$ 0 1 ... 1 1 0 $B(a(j)x)$ 0 1 ... 1 1 1 $B' (a(i)b)$ 1 1 ... 1 sth>1 or $\infty$ sth $B' (a(j)x)$ 1 1 ... 1 1 1 or x 可知 $B(a(i)b)<B(a(j)x),B'(a(i)b)<B'(a(j)x)$
综上,原命题得证。
时间复杂度
视后缀数组的构造算法,$O(n \log n)$ 到 $O(n)$
实现细节
通过令 $\infty=n$,并且加入虚节点 $b'[n+1]>n$ 的方式,通过普通后缀数组模板实现排序。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=3000020;
char ts[N];
int s[N];
int n,sa[N],rk[N],oldrk[N << 1],id[N],px[N],cnt[N];
bool cmp(int x,int y,int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
void solve()
{
int l[2]={n+1,n+1};
for(int i=n;i>0;i--)
{
s[i]=((l[ts[i]-'a']>n?n:l[ts[i]-'a']-i));
l[ts[i]-'a']=i;
}
n++;
s[n]=n;
int i,m=n+3,p,w;
for(int i=0;i<=n+5;i++)
{
sa[i]=rk[i]=oldrk[i]=oldrk[i+n+5]=id[i]=px[i]=cnt[i]=0;
}
for(i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
for(w=1;w<n;w<<=1,m=p)
{
for(p=0,i=n;i>n-w;--i) id[++p]=i;
for(i=1;i<=n;++i) if(sa[i]>w) id[++p]=sa[i]-w;
for(i=0;i<=n;++i) cnt[i]=0;
for(i=1;i<=n;++i) ++cnt[px[i]=rk[id[i]]];
for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(i=n;i>=1;--i) sa[cnt[px[i]]--]=id[i];
for(i=0;i<=min(N-1,2*n+5);++i) oldrk[i]=rk[i];
for(p=0,i=1;i<=n;++i) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
for(i=n-1;i>=1;--i) printf("%d ",sa[i]);
printf("\n");
}
int main(void)
{
while(~scanf("%d",&n))
{
scanf("%s",ts+1);
solve();
}
return 0;
}
B.Infinite Tree
lmj (赛后)
题意
给定一张图,mindiv(n)为n的最小的除数,n与n/mindiv(n)之间有一条长度为1的边,求一个点u使得$\sum_1^mw_i*dis(u,i!)$最小
题解
可以认为u是$x_1*x_2*x_3*x_4……$,同时是递减的,即为从根1走到$x_1$后再走到$x_1*x_2$,那么考虑枚举质数和每种质数的个数,考虑走到某个地方能否使得答案是减少的,可以确定该答案是一个区间,在不断缩小后即可以得到答案
代码
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
vector<int>v[N];
bool prime[N];
ll w[N];
ll sum[N];
void pre(int n)
{
for(int i=2;i<=n;i++){
if(!prime[i]){
for(int j=i;j<=n;j+=i){
if(i!=j)prime[j]=1;
int tmp=j;
while(tmp%i==0){
tmp/=i;
v[i].push_back(j);
sum[j]++;
}
}
}
}
for(int i=1;i<=n;i++){
sum[i]+=sum[i-1];
}
}
void work()
{
pre(1e5);
int n;
while(~scanf("%d",&n)){
ll cnt=0;
for(int i=1;i<=n;i++){
scanf("%lld",&w[i]);
cnt-=w[i];
w[i]+=w[i-1];
}
ll ans=0;
for(int i=1;i<=n;i++){
ans+=(w[i]-w[i-1])*sum[i];
}
int l=1,r=n;
for(int i=n;i>=2;i--){
if(!prime[i]){
for(int j=0;j<v[i].size();j++){
int x=v[i][j];
if(x>n)break;
if(x>l){
ll tmp=(w[x-1]-w[l-1])*2;
if(cnt+tmp>=0){
if(r>=x){
cnt+=(w[r]-w[x-1])*2;
r=x-1;
}
break;
}
cnt+=tmp;
l=x;
}
//printf("%d\n",ans);
ans+=cnt;
}
if(cnt>=0)break;
}
}
printf("%lld\n",ans);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
//scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}
D.Quadratic Form
lmj (赛后)
题意
$x_1,x_2,……,x_n$属于$R$,要求$\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j \le 1$,并且$\sum_{i=1}^nb_ix_i$最大,求$(\sum_{i=1}^nb_ix_i)^2$的值模998244353
题解
考虑使用拉格朗日乘数法
$$ f\left(x_{1}, x_{2}, \cdots, x_{n}, \lambda\right)=\sum_{i=1}^{n}\left(b_ix_{i}\right)+\lambda\left(\sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij} x_{i} x_{j}-t\right) \quad t \leqslant 1 $$
求偏导
$$ \left\{\begin{array}{l}b_{1}+2 \lambda\left(a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1n} x_{n}\right)=0 \\ b_{2}+2 \lambda\left(a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 n} x_{n}\right)=0 \\ b_{n}+2 \lambda\left(a_{n 1} x_{1}+a_{n 2} x_{2}+\cdots++a_{n n} x_{n}\right)=0 \\ \sum_{i=1}^{n} \sum_{j=1}^{n}\left(a_{i j} x_{i} x_{j}\right)=t\end{array}\right. $$
可得
$$ \left\{\begin{array}{l}B+2 \lambda A x=0 \\ x^{\top} A x=t\end{array}\right. $$
$$ \begin{array}{l}\because B+2 \lambda A X=0 \Rightarrow 2 \lambda A X=-B \Rightarrow X=-\frac{A^{-1} B}{2 \lambda} \\ \because B^{T} x=-B^{T} \frac{A^{\top}}{2 \lambda} B=X^{T} B \Rightarrow x^{T}=-B \frac{T{A^{-1}}}{2 \lambda}\end{array} $$
代入运算可得
$$ \begin{aligned}-B \frac{T A^{-1}}{2 \lambda} \cdot A \cdot\left(-\frac{A^{-1} B}{2 \lambda}\right) &=t \\ \frac{B^{\top} A^{-1} B}{4 \lambda^{2}} &=t \end{aligned} $$
$$ \begin{aligned}\left(\sum_{i=1}^{n} b_{i} x_{i}\right)^{2}=\left(B^{\top} x\right)^{2} &=\left(-\frac{1}{2 x} \cdot B^{\top} \cdot A^{-1} \cdot B\right)^{2} \\ &=\frac{1}{4\lambda^{2}} \cdot\left(B^{\top} A^{-1} \cdot B\right)^{2} \\ &=t \cdot\left(B^{\top} \cdot A^{-1} \cdot B\right) \end{aligned} $$
$$ \begin{array}{l} \because t \leq 1 \\ \therefore t 取1时最大 \\ 最大值为 B^{T} \cdot A^{-1} \cdot B\end{array} $$
代码
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const ll mod=998244353;
ll a[410][410];
ll b[410];
ll c[410];
int n,is[410],js[410];
void exgcd(int a,int b,int &x,int &y){
if(!b)return x=1,y=0,void();
exgcd(b,a%b,y,x);y-=x*(a/b);
}
int inv(int p){
int x,y;exgcd(p,mod,x,y);
return (x+mod)%mod;
}
void inv(){
for(int k=1;k<=n;k++){
for(int i=k;i<=n;i++) // 1
for(int j=k;j<=n;j++)if(a[i][j]){
is[k]=i,js[k]=j;break;
}
for(int i=1;i<=n;i++) // 2
swap(a[k][i],a[is[k]][i]);
for(int i=1;i<=n;i++)
swap(a[i][k],a[i][js[k]]);
if(!a[k][k]){
puts("No Solution");
exit(0);
}
a[k][k]=inv(a[k][k]); // 3
for(int j=1;j<=n;j++)if(j!=k) // 4
(a[k][j]*=a[k][k])%=mod;
for(int i=1;i<=n;i++)if(i!=k) // 5
for(int j=1;j<=n;j++)if(j!=k)
(a[i][j]+=mod-a[i][k]*a[k][j]%mod)%=mod;
for(int i=1;i<=n;i++)if(i!=k) // 就是这里不同
a[i][k]=(mod-a[i][k]*a[k][k]%mod)%mod;
}
for(int k=n;k;k--){ // 6
for(int i=1;i<=n;i++)
swap(a[js[k]][i],a[k][i]);
for(int i=1;i<=n;i++)
swap(a[i][is[k]],a[i][k]);
}
}
void work()
{
while(~scanf("%d",&n)){
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
memset(is,0,sizeof(is));
memset(js,0,sizeof(js));
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%lld",&a[i][j]);
a[i][j]=(a[i][j]%mod+mod)%mod;
}
}
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
b[i]=(b[i]%mod+mod)%mod;
}
inv();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
c[i]=(c[i]+a[j][i]*b[j]%mod)%mod;
}
}
for(int i=1;i<=n;i++){
c[i]=(c[i]*b[i])%mod;
}
ll ans=0;
for(int i=1;i<=n;i++){
ans=(ans+c[i])%mod;
}
printf("%lld\n",(ans+mod)%mod);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
//scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}
E.Counting Spanning Trees
zyj (赛后)
题意:
给定一张(n+m)个点的图,点为$ x_1,x_2,...,x_n $和$ y_1,y_2,...y_m $
节点$x_i$和$y_1,y_2,...,y_{a_i}$有边
给出n,m和$a_i$,问生成树数量
题解:
由论文可得,答案为:
$sort(deg(x_i))$
$\prod_{i < n} deg(x_i) * \prod_{i >= 2} deg(y_i)$
代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
int n,m,mod;
ll a[maxn],c[maxn];
void solve(){
rep(i,1,n) scanf("%lld",&a[i]);
sort(a+1,a+1+n);
rep(i,1,m+1) c[i]=0;
rep(i,1,n) c[1]++,c[a[i]+1]--;
rep(i,1,m+1) c[i]+=c[i-1];
ll ans=1;
rep(i,1,n-1) (ans*=a[i])%=mod;
rep(i,2,m) (ans*=c[i])%=mod;
printf("%lld\n",ans);
}
int main(){
while(~scanf("%d%d%d",&n,&m,&mod)) solve();
}
F.Infinite String Comparision
wrf (00:28:15) +0
题意
给出两个无限循环串的循环节,比较两个串的大小。
两循环节长度均不超过 $10^5$
题解
做法
令两循环节分别为 $p,q$。模拟题意,比较两字符串直到第 $$|$p$|$+$|$q$|$-gcd($|$p$|$,$|$q$|$)$ 个字符为止。
证明
以下记号不区分串和串长
首先给出 Periodicity Lemma:
假设一个字符串 $S$ 有循环节(不需要是完整循环节) $p$ 和 $q$,并且满足 $p+q \leq S+\gcd(p,q)$,那么 $\gcd(p,q)$ 也是一个循环节。
记由串 $k$ 无限循环得到的串为 $k^{\infty}$。记串 $S$ 到第 $i$ 位的前缀为 $pre_{S,i}$。令 $S_p=pre_{p^\infty,p+q-\gcd(p,q)}$,$S_q=pre_{q^\infty,p+q-\gcd(p,q)}$。
当 $S_p \not = S_q$ 时答案显然。下面证当 $S_p=S_q$ 时,必有 $p^\infty=q^\infty$:
令 $S=S_p=S_q$,由 Periodicity Lemma,$S$ 存在循环节 $\gcd(p,q)$,并且它显然是 $S$ 的一个完整循环节。
由此易得,$\gcd(p,q)$ 也是 $p,q,p^\infty,q^\infty$ 的完整循环节,并且已经验证了 $pre_{p^\infty,\gcd(p,q)}=pre_{q^\infty,\gcd(p,q)}$,所以 $p^\infty=q^\infty$。
时间复杂度
显然 $O(n)$
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100020;
char c1[N],c2[N];
char solve()
{
int n=strlen(c1);
int m=strlen(c2);
for(int i=0;i<2*max(n,m);i++) //懒惰,直接*2了
{
if(c1[i%n]<c2[i%m]) return '<';
else if(c1[i%n]>c2[i%m]) return '>';
}
return '=';
}
int main(void)
{
while(~scanf("%s",c1))
{
scanf("%s",c2);
printf("%c\n",solve());
}
return 0;
}
G.BaXianGuoHai, GeXianShenTong
lmj (赛后)
题意
给出一个三元组$(x_0,x_1,x_2)$,设定乘法运算为$(x_0,x_1,x_2)*(y_0,y_1,y_2)=(x_0*y_0+x_1*y_2+x_2*y_1,\\x_1*y_0+x_2*y_2+x_0*y_1,\\x_2*y_0+x_0*y_2+x_1*y_1)$
现在给定n个三元组,和q组n个的e,求$(x_{10},x_{11},x_{12})^{e_{11}}*(x_{20},x_{21},x_{12})^{e_{12}}*……*(x_{n0},x_{n1},x_{n2})^{e_{1n}}\\(x_{10},x_{11},x_{12})^{e_{21}}*(x_{20},x_{21},x_{12})^{e_{22}}*……*(x_{n0},x_{n1},x_{n2})^{e_{2n}}\\……\\(x_{10},x_{11},x_{12})^{e_{q1}}*(x_{20},x_{21},x_{12})^{e_{q2}}*……*(x_{n0},x_{n1},x_{n2})^{e_{qn}}$
题解
可以证明该三元组满足交换律和结合律,同时单位元为(1,0,0),满足快速幂,但是幂次可以达到$2^{300}$存不下,使用JAVA或者PYTHON大数也显然会T,然后选择将幂次对$p*p-1$进行取模(别问我为什么,我也不知道),然后就好做了。
代码
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=998244353;
ll e[25][N];
__int128 pre[405];
__int128 mo=1ll*p*p-1;
struct node
{
ll x,y,z;
node operator *(const node &a)const{
return {(x*a.x+y*a.z+z*a.y)%p,(y*a.x+z*a.z+x*a.y)%p,(z*a.x+x*a.z+y*a.y)%p};
}
}v[N];
node qpow(node a,ll n)
{
node res;
res.x=1;
res.y=0;
res.z=0;
while(n){
if(n&1)res=res*a;
a=a*a;
n>>=1;
}
return res;
}
void work()
{
pre[0]=1;
for(int i=1;i<=400;i++){
pre[i]=pre[i-1]*2%mo;
}
int n,m,q,z0,a,b;
scanf("%d%d%d%d%d%d",&n,&m,&q,&z0,&a,&b);
ll z=z0;
for(int i=1;i<=n;i++){
z=(z*a+b)%pre[32];
v[i].x=z%p;
z=(z*a+b)%pre[32];
v[i].y=z%p;
z=(z*a+b)%pre[32];
v[i].z=z%p;
}
for(int k=1;k<=q;k++){
for(int i=1;i<=n;i++){
e[k][i]=0;
for(int j=0;j<m;j++){
z=(z*a+b)%pre[32];
__int128 tmp=z;
tmp=tmp*pre[32*j]%mo;
e[k][i]=(e[k][i]+tmp)%mo;
}
}
}
for(int i=1;i<=q;i++){
node res;
res.x=1;
res.y=0;
res.z=0;
for(int j=1;j<=n;j++){
res=res*qpow(v[j],e[i][j]);
}
printf("%lld %lld %lld\n",res.x,res.y,res.z);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
//scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}
H.Minimum-cost Flow
lmj (01:35:09) +2
题意
给定网络的边和费用,每次询问给定所有边的容量u和要求的流量v,问最少所需要的费用,如果不能满流输出NaN
题解
由于所有边的容量相同,所以可以得到一个性质,$k*u$的流量在图中形成了k条1-n的路径,每多u的流量多形成一条路径(可能会导致原路径改变,但是只会在$k*u$到$k*u+1$时发生改变),这u的流量所用的花费是相同的,所以考虑u和v的倍数关系,预处理出u为1,v从1到100的花费,然后询问时直接求出对应的花费
代码
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
struct ZKW_SPFA{
#define maxn 201
#define maxe 5005
const ll INF=1e18;
ll dis[maxn],vis[maxn],head[maxn],tot;
ll n,Cost=0,Flow=0;
struct Edge{ll v,cap,cost,nxt;}g[maxe<<1];
void init(ll _n){tot=Cost=Flow=0;memset(head,-1,sizeof(head));n=_n;}
void add(ll u,ll v,ll cap,ll cost){
g[tot]={v,cap,cost,head[u]};head[u]=tot++;
}
void addedge(ll u,ll v,ll cap,ll cost){
add(u,v,cap,cost);add(v,u,0,-cost);
}
bool spfa(ll S,ll T){
for(ll i=0;i<=n;i++) vis[i]=0,dis[i]=INF;
deque<ll>Q;Q.push_back(T);dis[T]=0;vis[T]=1;
while(!Q.empty()){
ll u=Q.front();Q.pop_front();
for(ll i=head[u],v;~i;i=g[i].nxt)
if(g[i^1].cap&&dis[v=g[i].v]>dis[u]+g[i^1].cost){
dis[v]=dis[u]+g[i^1].cost;
if(!vis[v]){
vis[v]=1;
if(!Q.empty()&&dis[v]<dis[Q.front()]) Q.push_front(v);
else Q.push_back(v);
//SLF???
}
} vis[u]=0;
} return dis[S]<INF;
}
ll dfs(ll S,ll T,ll flow){
if(S==T){vis[T]=1;return flow;}
ll used=0,res;vis[S]=1;
for(ll i=head[S],v;~i;i=g[i].nxt)
if(!vis[v=g[i].v]&&g[i].cap&&dis[S]-g[i].cost==dis[v]){
res=dfs(v,T,min(g[i].cap,flow-used));
if(res) Cost+=res*g[i].cost,g[i].cap-=res,g[i^1].cap+=res,used+=res;
if(used==flow)break;
}
return used;
}
void solve(ll S,ll T){
while(spfa(S,T)){
vis[T]=1;
while(vis[T]) memset(vis,0,sizeof vis),Flow+=dfs(S,T,INF);
}
}
//?zkw.init(n),?zkw.addedge(),?zkw.solve(S,T)
//????zkw.Flow??kw.Cost
}zkw;
ll ans[105];
ll x[105],y[105],z[105];
void work()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
zkw.init(n+2);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
}
int limit=0;
for(int i=1;i<=101;i++){
zkw.init(n+2);
zkw.addedge(n+1,1,i,0);
for(int j=1;j<=m;j++){
zkw.addedge(x[j],y[j],1,z[j]);
}
zkw.solve(n+1,n);
ans[i]=zkw.Cost;
if(zkw.Flow!=i){
limit=i-1;break;
}
}
int q;
scanf("%d",&q);
while(q--){
ll u,v;
scanf("%lld%lld",&u,&v);
if(u*limit<v){
printf("NaN\n");continue;
}
ll sum=ans[v/u]*u;
ll tmp=v%u;
sum+=(ans[v/u+1]-ans[v/u])*tmp;
ll tmp1=__gcd(sum,v);
sum/=tmp1;
v/=tmp1;
printf("%lld/%lld\n",sum,v);
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
//scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}
I.1 or 2
zyj (赛后)
题意
给出一张图和每个点的期望度数,要求你删掉一些边使得每个点的度数都等于期望度数,问是否可行。
题解
我们考虑匹配问题,每条边会关联两个点,那么肯定是点和边有关联;每个点需要减的度数是$deg(v_i) - d_i$,因此每个点拆成$deg(v_i) - d_i$个点,然后每条边拆成两个点$e_i$和$e_i '$,连完边之后这就是一个二分图,跑完图匹配之后必定还有某些边没有匹配上(因为每一个拆出来的点都会连$deg(v_i)$条边,最大的情况也不过是全部都匹配上);
但是我们对于边拆出来的点也有限制,就是它只能被匹配0次或者2次(匹配一次说明一条边只关联了一个点,不符合现实);
那么现在的问题就是如何判断边拆出来的点不会匹配1个点,那么我们把$e_i$和$e_i '$连一条边,这样的话如果有一条边没有被用到那么这条边会形成一个匹配,满足题意。
J.Easy Integration
lmj (00:11:02) +0
题意
求 $\int_0^1(x-x^2)^ndx$ 输出分数p/q为$p*q^{-1}$%998244353
题解
oeis的 并不会证 答案为 $(n!)^2/(2n+1)!$
补:欧拉积分 $\int_0^1x^n(1-x)^ndx=B(n+1,n+1)=\frac{n*n}{(2*n+1)(2*n)}*B(n,n)$,最后即可得到上式
本文由 Edwiv 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Aug 1, 2020 at 11:47 am
太菜了,被学弟爆踩