四道数论题

目录

• T1 P3232 [HNOI2013]游走
• T2 P3214 [HNOI2011]卡农
• T3 CF722F Cyclic Cipher
• T4 P4240 毒瘤之神的考验

T1 P3232 [HNOI2013]游走

题目大意
给定一张无向图，从\(1\)号点开始每次等概率地走向与它联通的点，直到走到\(n\)号点为止，求在最好的对\(m\)条边进行\(1\)~\(m\)标号方案之下，第\(i\)条边的期望次数\(×\)它的标号之和的最小值。
\(2≤n≤500，1 \leq m \leq 125000\)
Sol
做过类似的题的话就很好想到是一道高斯消元的题。
所谓标号其实只是一个幌子，明显是将每条边期望经过次数排序以后按从大到小标号计算即可。
设\(f[i]\)表示第\(i\)个点期望经过次数。那么很容易得到式子如下

\[f[i]=\sum_{u=i}\frac{f[v]}{deg[v]}+1(i=1)\\f[i]=\sum_{u=i}\frac{f[v]}{deg[v]}(i≠1)\\ \]

\(f[n]\)显然没有意义，因为\(n\)号点是只进不出的。
所以可以对前\(n-1\)个点跑高斯消元
设\(g[i]\)表示第\(i\)条边的期望经过次数。那么有

\[g[i]=\frac{f[u_i]}{deg[u_i]}+\frac{f[v_i]}{deg[v_i]} \]

时间复杂度\(O(n^2+mlogm)\)。
Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
    return x*f;
}
double abss(double x)
{
    if(x>=0)return x;
    return -x;
}
double a[510][510];
double b[510],c[125010];
int deg[510];
struct edge
{
    int to,next;
}e[250010];
int h[510],ei=1;
inline void add(int x,int y)
{
    e[++ei]=(edge){y,h[x]};
    h[x]=ei;return;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        deg[x]++;deg[y]++;
        add(x,y);add(y,x);
    }
    a[1][1]=1.0;
    for(int i=h[1];i;i=e[i].next)
    {
        int to=e[i].to;
        if(to==n)continue;
        a[1][to]=-1.0/deg[to];
    }
    a[1][n]=1.0;
    for(int i=2;i<n;i++)
    {
        a[i][i]=1.0;
        for(int j=h[i];j;j=e[j].next)
        {
            int to=e[j].to;
            if(to==n)continue;
            a[i][to]=-1.0/deg[to];
        }
    }
    for(int i=1;i<n;i++)
    {
        int maxm=i;
        for(int j=i+1;j<n;j++)
        {
            if(abss(a[j][i])>abss(a[maxm][i]))maxm=j;
        }
        for(int j=1;j<n+1;j++)
        {
            swap(a[i][j],a[maxm][j]);
        }
        if(!a[i][i])return printf("No Solution\n")&0;
        for(int j=1;j<n;j++)
        {
            if(j==i)continue;
            double bei=a[j][i]/a[i][i];
            for(int k=i+1;k<n+1;k++)
            {
                a[j][k]-=bei*a[i][k];
            }
        }
    }
    for(int i=1;i<n;i++)
    {
        b[i]=a[i][n]/a[i][i];
    }
    for(int i=2;i<=ei;i+=2)
    {
        int x=e[i^1].to,y=e[i].to;
        c[i/2]=1.0*b[x]/deg[x]+1.0*b[y]/deg[y];
    }
    sort(c+1,c+m+1);
    double ans=0.0;
    for(int i=1;i<=m;i++)
    {
        ans+=c[i]*1.0*(m-i+1);
    }
    printf("%.3lf",ans);
    return 0;
}

T2 P3214 [HNOI2011]卡农

题目大意
求出从\({1,2,…,n}\)的所有非空子集中选出\(m\)个不同的子集，满足\(1\)~\(n\)每个数出现的次数均为偶数的方案数。
\(1 \leq n,m \leq 10^6\)
Sol
如果不看题解的话思维难度很高，我直接推只能想出来第一部分。
设\(f[i]\)表示选取\(i\)个子集的合法方案数。
很容易想到选定前\(i-1\)个子集以后，第\(i\)个子集已经确定，前\(i-1\)个子集的选择方案有\(P_{2^n-1}{i-1}\)种。
考虑删去其中不符合条件的部分：
1、最后第\(i\)个集合为空，说明前\(i-1\)个子集是合法的，故减去\(f[i-1]\)
2、由于前\(i-1\)个子集互不相同，考虑第\(i\)个子集与第\(j(1 \leq j < i)\)个子集相同的情况。那么去掉这两个集合后的取法也合法，\(j\)有\(i-1\)种选取方式，\(i\)有\(2^n-i+1\)种选取方式。故还要减去\(f[i-2]*(i-1)*(2^n-i+1)\)。
综上可得\(f[i]=P_{2^n-1}{i-1}-f[i-1]-f[i-2]*(i-1)*(2^n-i+1)\)。
由于排列的下标始终为\(2^n-1\)，因此可以直接预处理计算。
Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e8+7,maxn=1000010;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
    return x*f;
}
int n,m;
int pp[maxn],f[maxn],erd;
inline int ksm(int x,int mi)
{
    int ans=1;
    while(mi)
    {
        if(mi&1)ans=ans*x%p;
        x=x*x%p;mi>>=1;
    }
    return ans;
}
signed main()
{
    n=read();m=read();
    int err=erd=ksm(2,n);
    pp[0]=1;
    for(int i=1;i<=m;i++)
    {
        erd--;
        if(erd==0)break;
        pp[i]=pp[i-1]*erd%p;
    }
    f[0]=1;
    for(int i=2;i<=m;i++)
    {
        f[i]=pp[i-1];
        if(i)f[i]=(f[i]-f[i-1]+p)%p;
        if(i>1)f[i]=(f[i]-(i-1)*(err-i+1)%p*f[i-2]%p+p)%p;
    }
    int jc=1;
    for(int i=2;i<=m;i++)jc=jc*i%p;
    jc=ksm(jc,p-2);
    cout<<f[m]*jc%p;
    return 0;
}

T3 CF722F Cyclic Cipher

题目大意
给定\(n\)个序列，每个序列长度为\(k_i\)且每个数\(\leq m\)，每次将各个序列的顶部的数取下来放到该序列的尾部，并记录下由新序列顶部组成的数组。求在\(10^{100}\)次操作以后对于\(1\leq i \leq m\)在每次记录的数组中出现的最长连续长度。
\(1 \leq n,m \leq 10^5\;\; 1 \leq k_i \leq 40\)
Sol
贺题大法好啊
反正就是用尺取法干就完了！
Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
    return x*f;
}
const int maxn=100010;
vector<int>a[maxn];
map<int,vector<pair<int,int> > >b;
int T[maxn],cnt[50],sk[50];
inline int gcd(int x,int y)
{
    while(y)
    {
        int t=y;y=x%y;x=t;
    }
    return x;
}
inline bool check(int tid,int x)
{
    for(int i=1;i<=40;i++)
    {
        if(cnt[i]&&(sk[i]-x)%gcd(i,tid))return false;
    }
    sk[tid]=x;cnt[tid]++;
    return true;
}
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        T[i]=read();
        for(int j=1;j<=T[i];j++)
        {
            int ls=read();
            a[i].push_back(ls);
            b[ls].push_back(pair<int,int>(i,j));
        }
    }
    int l,r,ans;
    for(int i=1;i<=m;i++)
    {
        ans=0;memset(cnt,0,sizeof(cnt));
        int si=b[i].size();
        for(l=0,r=0;l<si;l++)
        {
            for(;r<si&&b[i][r].first-b[i][l].first==r-l;r++)
            {
                if(!check(T[b[i][r].first],b[i][r].second))break;
            }
            cnt[T[b[i][l].first]]--;
            ans=max(ans,r-l);
        }
        printf("%d\n",ans);
    }
    return 0;
}

T4 P4240 毒瘤之神的考验

题目大意
多组询问，求\(\sum_{i=1}^n\sum_{j=1}^m \varphi(ij)\)
\(1\leq T\leq 10^4\;\;1\leq n,m\leq 10^5\)
Sol
明天再来