1006.A-Very-Easy-Graph-Problem

标签：并查集，树形dp

思考关键点是按照边给出的顺序，如果当前的两个点本来就是连通的，那么这条边肯定不起作用，直接忽略。如果这两个点不连通，就连一条边。判断联通可以用并查集实现。

最后肯定连成一棵树，然后树形dp，记录每颗子树0和1的个数，以及所有0和1到达子树根节点的路径长就可以dp转移了。

还有一种做法就是枚举边，记录每条边两侧0和1的数量，得到这条边被经过的次数，次数×权值计算贡献。

#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;

const int N=2e5+5,MOD=1e9+7;

int T,n,m,tmp;

int fa[N],a[N];

long long cnt[N][2],sum[N][2],ans;

struct Edge{
    int to,v;
};
vector<Edge>G[N];

int getfa(int x) {
    if (fa[x]==x) return x;
    else return fa[x]=getfa(fa[x]);
}

void init() {
    ans=0;
    for (int i=1;i<=n;i++) {
        G[i].clear();
        fa[i]=i;
        cnt[i][0]=cnt[i][1]=0;
        sum[i][0]=sum[i][1]=0;
    }
}

void dfs(int x,int f) {
    if (G[x].size()==1 && ~f) {
        cnt[x][a[x]]++;
        return;
    }
    for (auto t:G[x]){
        int to=t.to,v=t.v;
        if (to==f) continue;
        dfs(to,x);
        cnt[x][0]+=cnt[to][0];cnt[x][1]+=cnt[to][1];
        cnt[x][0]%=MOD;cnt[x][1]%=MOD;
        sum[x][0]=(sum[x][0]+sum[to][0]+1ll*v*cnt[to][0])%MOD;
        sum[x][1]=(sum[x][1]+sum[to][1]+1ll*v*cnt[to][1])%MOD;
    }
    for (auto t:G[x]){
        int to=t.to,v=t.v;
        if (to==f) continue;
        ans=(ans+(cnt[x][0]-cnt[to][0]+MOD)%MOD*cnt[to][1]*v)%MOD;
        ans=(ans+(cnt[x][1]-cnt[to][1]+MOD)%MOD*cnt[to][0]*v)%MOD;
        ans=(ans+(sum[to][0]*(cnt[x][1]-cnt[to][1]+MOD)%MOD))%MOD;
        ans=(ans+(sum[to][1]*(cnt[x][0]-cnt[to][0]+MOD)%MOD))%MOD;
        ans=(ans+1ll*cnt[to][1-a[x]]*v+sum[to][1-a[x]])%MOD;
    }
    cnt[x][a[x]]=(cnt[x][a[x]]+1)%MOD;
}

int main() {
    cin>>T;
    while(T--) {
        scanf("%d%d",&n,&m);
        init();
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        tmp=2;
        for (int i=1;i<=m;i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            if (getfa(u)!=getfa(v)){
                G[u].push_back({v,tmp});
                G[v].push_back({u,tmp});
                fa[getfa(v)]=getfa(u);
            }
            tmp=(1ll*tmp*2)%MOD;
        }
        dfs(1,-1);
        printf("%lld\n",ans);
    }
    return 0;
}

1010.Expectation

标签：位运算、生成树计数、计算行列式

把每一位拆开来分别计算贡献。

先把所有边都连上计算出生成树的总和tot，然后把当前位为1的边再建个图计算新图生成树的个数cnt，那么第i位对答案的贡献就为$1<<(i-1)\times\frac{cnt}{tot}$

关键在于怎么计算生成树的个数。其实我也不会，临时去搜了个板子。

其实就是根据图构造一个行列式，满足

$a_{ij}=\begin{cases}deg[i] &i==j\\ -1&i、j之间存在一条边\\ 0&i、j之间没有边\end{cases}$

然后去掉一个点的信息（比如这里去掉的是第n行第n列）之后算一下行列式的值就是生成树的个数了。

这题应该还需要考虑重边的情况，方法就是i、j之间每有一条边，$a_{ij}$就减1。

#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
#define LL long long
using namespace std;

const int MOD=998244353,MAXN=1e2+5;

LL a[MAXN][MAXN],ans;

int T,n,m,sign;

int M[MAXN][MAXN],M2[MAXN][MAXN];

int bin(int base,int p) {
    int res=1;
    for (;p;p>>=1,base=(1ll*base*base)%MOD)
        if (p&1) res=(1ll*res*base)%MOD;
    return res;
}

struct Edge{
    int u,v,w;
}e[10005];
LL solve(int N){
    sign = 0; LL ans = 1;
    for(int i=1; i<N; i++){
        for(int j=i+1; j<N; j++){//当前之后的每一行第一个数要转化成0
            int x=i, y=j;
            while( a[y][i] ){//利用gcd的方法，不停地进行辗转相除
                LL t = a[x][i] / a[y][i];
                for(int k=i; k<N; k++)
                    a[x][k] = (a[x][k] - a[y][k] * t) % MOD;
                swap(x, y);
            }
            if(x != i){//奇数次交换，则D=-D'整行交换
                for(int k=1; k<N; k++)
                    swap(a[i][k], a[x][k]);
                sign ^= 1;//行列式*-1
            }
        }
        if( !a[i][i] ){//斜对角中有一个0，则结果为0
            return 0;
        }
        else ans = ans * a[i][i] % MOD;
    }
    if(sign != 0) ans *= -1;
    if(ans < 0) ans += MOD;//
    return ans;
}

int main(){
    cin>>T;
    while(T--) {
        scanf("%d%d",&n,&m);
        memset(M,0,sizeof(M));
        for (int i=1;i<=m;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            e[i].u=u;e[i].v=v;e[i].w=w;
        }
        memset(a,0,sizeof(a));
        for (int k=1;k<=m;k++) {
            int i=e[k].u,j=e[k].v;
            a[i][i]++;a[j][j]++;
            a[i][j]--;a[j][i]--;
        }
        LL tot=solve(n);
        tot=bin(tot,MOD-2);
        ans=0;
        for (int i=0;i<=30;i++)
        {
            memset(M2,0,sizeof(M2));
            /*for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    M2[j][k]=M[j][k]&(1<<i);*/
            memset(a,0,sizeof(a));
            for (int p=1;p<=m;p++) {
                if (e[p].w&(1<<i)) {
                    int j=e[p].u,k=e[p].v;
                    a[j][j]++;a[k][k]++;
                    a[j][k]--;a[k][j]--;
                }
            }
            LL cur=solve(n);
            ans=(ans+(1ll*cur*tot)%MOD*(1<<i))%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

1005.Fragrant-numbers

标签：思维、dp

关键点：先打个表，然后就会发现只有3和7不能构造，其他5000内的所有数答案都在13位以内。然后就用集合dp[l][r]表示从l到r能组成的所有数（只记录5000以内的），那么dp[l][r]就为dp[l][mid]和dp[mid+1][r]中每个数任意组合之后的和或积了。

#include<bits/stdc++.h>
using namespace std;

const int N=20,M=5e3+5;

const string s=".11451419191145141919";

int T,n;

set<int>dp[N][N];

int ans[M];

int getNum(int l,int r) {
    int res=0;
    for (int i=l;i<=r;i++) {
        res=res*10+s[i]-'0';
    }
    return res;
}

void dfs(int l,int r) {
    if (l>r) return;
    if (dp[l][r].size()) return;
    if (r-l<4) {
        int x=getNum(l,r);
        if (x<=5000) dp[l][r].insert(x);
    }
    for (int i=l;i<r;i++) {
        dfs(l,i);dfs(i+1,r);
        for (int u:dp[l][i]) for (int v:dp[i+1][r]) {
            if (u+v<=5000) dp[l][r].insert(u+v);
            if (u*v<=5000) dp[l][r].insert(u*v);
        }
    }
}

int main() {
    memset(ans,-1,sizeof(ans));
    dfs(1,13);
    for (int i=1;i<=13;i++) for (int x:dp[1][i])
        if (ans[x]==-1) ans[x]=i;
    cin>>T;
    while(T--) {
        int x;
        scanf("%d",&x);
        printf("%d\n",ans[x]);
    }
    return 0;
}

1007.A-Very-Easy-Math-Problem

标签：莫比乌斯反演

我其实很想把这题一起补了，但是实在是没有接触过莫比乌斯反演之类的题目（确切说，突然发现自己对所有数论的知识都完全没什么接触 ~~只会GCD~~）看了一天还是没搞出个所以然，只能暂时搁置先把其他题补了。尽快学一下数论的内容吧。。任务单+1