[CZYZ2016]day5

小W拼图

Description

小\(W\)和小\(M\)一起玩拼图游戏啦~
小\(M\)给小\(M\)一张\(N\)个点的图，有\(M\)条可选无向边，每条边有一个甜蜜值，小\(W\)要选\(K\)条边，使得任意两点间最多有一条路径，并且选择的\(K\)条边甜蜜值之和最大。

Input

第一行三个正整数\(N,M,K\)。
接下来\(M\)行，每行三个正整数\(A,B,C\)表示\(A,B\)两点间有一条甜蜜值为\(C\)的无向边。

Output

一行输出最大甜蜜值之和。

Sample Input

5 4 3 
1 2 10 
1 3 9 
2 3 7 
4 5 3

Sample Output

22

HINT

\(N,M\;\leq\;100000\)

Solution

\(kruskal\)裸题。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
using namespace std;
struct edge{
    int l,r,w;
}a[N];
int f[N],n,m,k,ans;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=ret*10+c-'0';
        c=getchar();
    }
    return ret;
}
inline bool cmp(edge x,edge y){
    return x.w>y.w;
}
inline int gf(int k){
    if(f[k]==k) return k;
    return f[k]=gf(f[k]);
}
inline void init(){
    n=read();m=read();k=read();
    for(int i=1;i<=m;i++){
        a[i].l=read();a[i].r=read();
        a[i].w=read();f[i]=i;
    }
    sort(a+1,a+1+m,cmp);
    for(int i=1,p,q;k&&i<=m;i++){
        p=gf(a[i].l);q=gf(a[i].r);
        if(p!=q){
            k--;ans+=a[i].w;f[p]=q;
        }
    }
    printf("%d\n",ans);
}
int main(){
    freopen("carpet.in","r",stdin);
    freopen("carpet.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

小M求和

Description

小\(W\)顺利地完成了拼图，该他给小\(M\)出题啦。
小\(W\)定义\("!"\)运算符：

1. \(N!k=N!(k-1)\;\times\;(N-1)!k\;(N>0\)且\(k>0)\)
2. \(N!k=1\;(N=0)\)
3. \(N!k=N\;(k=0)\)

现在小\(W\)告诉小\(M\;N\)和\(k\)，小\(M\)需要说出\(N!k\)的不同约数个数。
为了降低难度，答案对\(10^9+9\)取模就好了。

Input

第一行两个整数\(N,M\)。

Output

一行一个整数，为答案。

Sample Input

3 1

Sample Output

4

HINT

\(N\;\leq\;1000,k\;\leq\;100\)

Solution

• 解法一：

质因数分解一个数\(x\)为\(x=p_1^{a_1}p_2^{a_2}…p_k^{a_k}(p_i\)为不同的质数)

则\(x\)的不同约数个数为\((a1+1)(a2+1)…(ak+1)\)。

所以只需知道\(N!K\)的约数个数即可。

设\(f[i][j][k]\)为\(i!j\)的结果中，第\(k\)个质数的个数:

\(f[i][j][k]=f[i][j-1][k]+f[i-1][j][k](i>0\)且\(j>0)\)

\(f[i][j][k]=0(i=0)\)
\(f[i][j][k]=N\)分解质因数后的结果\((j=0)\)

• 解法二：

随便推推会发现和杨辉三角形很像，然后就很容易做了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define P 170
#define K 101
#define N 1001
#define M 1000000009
#define MOD 1000000009ll
using namespace std;
typedef long long ll;
struct total{
    int t[P];
}f[N][K];
ll ans;
int p[P],n,k,cnt;
bool b[N];
inline void prime(){
    for(int i=2;i

4 4 2 1 4 
1 2 2 1 
2 3 2 1 
3 4 5 1 
2 4 4 2 
3 2 
3 6 
10 5 3 
100 
10 9

54

#include
#include
#include
#include
#include
#include
#include
#include
#define C 25
#define P 55
#define N 105
#define M 20005
#define INF 2000000
using namespace std;
int q[C][P],r[C][P],p[C];
int a[C][N][N],dis[N][N],n,m,c,s,t;
inline int cost(int len,int t){
    int c=0;
    for(int i=1;iq[t][p[t]-1])
        c+=(len-q[t][p[t]-1])*r[t][p[t]];
    return c;
}
inline void floyd1(){
    int d[N][N];
    for(int l=1;l<=c;l++){
        for(int i=1;i