## 【Codeforces 800C】Vulnerable Kerbals

### Code

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

const int N = 5000000;
const int M = 10000;

int n,m,tot,ans,vis[N],id[N],in[M],num[M];
vector<int> que[M],vout;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int gcd(int a, int b) {
return b? gcd(b, a%b): a;
}

inline void AddEdge(int u, int v) {
static int E = 1; in[u]++;
}

void solve(int w) {
f[w] = que[w].size() + (itr[w]?f[itr[w]]:0);
ans = max(ans, f[w]);
if (f[w] > f[itr[to[i]]]) itr[to[i]] = w;
if (--in[to[i]] == 0) solve(to[i]);
}
}

void exgcd(int a, int b, LL &x, LL &y) {
if (b) {exgcd(b, a%b, y, x); y -= a / b * x;}
else {x = 1; y = 0;}
}

inline int REV(int a, int z) {
int tmp = gcd(a, m), b; LL x, y;
a /= tmp; z /= tmp; b = m / tmp;
exgcd(a, b, x, y);
return x * z % m;
}

void print(int w, int v) {
for (int i=0;i<=que[w].size()-1;i++) {
int nv = que[w][i], rev = REV(v, nv);
vout.push_back((rev+m)%m); v = nv;
}
if (itr[w]) print(itr[w], v);
}

int main() {
for (int i=1;i<=n;i++) vis[read()] = 1;
for (int i=1;i<m;i++) if (!vis[i]) {
int tmp = gcd(m, i);
if (!id[tmp]) id[tmp] = ++tot, num[tot] = tmp;
que[id[tmp]].push_back(i);
}
for (int i=1;i<=tot;i++) {
for (int j=1;j<=tot;j++) {
if (num[j] > num[i] && num[j] % num[i] == 0) {
}
}
}
for (int i=1;i<=tot;i++) if (!in[i]) solve(i);
for (int i=1;i<=tot;i++) if (f[i] == ans) {print(i, 1); break;}
if (!vis[0]) vout.push_back(0); cout<<vout.size()<<endl;
for (int i=0;i<=vout.size()-1;i++) printf("%d ",vout[i]);
return 0;
}


## 【日常小测】题目1

### 题目大意

$n \le 1e18, k \le 1e5$

### 解题报告

$$\sum_{j=0}^{k}{(-1)^{k-j} \cdot C_k^j \sum_{i-1}^n{(A^jB^{k-j})^i}}$$

### Code

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

const int MOD = 1000000009;
const int A = 691504013;
const int B = 308495997;
const int REV_SQRT_FIVE = 276601605;
const int N = 100009;

int k,vout,PA[N],PB[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, LL t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t & 1) ret = (LL)ret * w % MOD;
return ret;
}

inline int Mul(int a, LL b) {
int ret = 0;
for (;b;b>>=1,(a<<=1)%=MOD)
if (b & 1) (ret += a) %= MOD;
return ret;
}

int main() {
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
LL n; cin>>n; k = read();
PA[0] = PB[0] = 1;
for (int i=1;i<=k;i++) {
PA[i] = (LL)PA[i-1] * A % MOD;
PB[i] = (LL)PB[i-1] * B % MOD;
}
for (int i=0,c=1,v;i<=k;i++) {
v = (LL)PA[i] * PB[k-i] % MOD;
if (v == 1) v = Mul(v, n);
else v = ((LL)Pow(v, n+1) - v) * Pow(v-1, MOD-2) % MOD;
if (k-i & 1) (vout -= (LL)c * v % MOD) %= MOD;
else (vout += (LL)c * v % MOD) %= MOD;
c = ((LL)c * (k - i) % MOD) * Pow(i+1, MOD-2) % MOD;
}
printf("%d\n",((LL)vout*Pow(REV_SQRT_FIVE,k)%MOD+MOD)%MOD);
return 0;
}


## 【Codeforces 715C】Digit Tree

### Code

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

const int N = 200000 + 9;

int n,MOD; LL vout;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void gcd(int a, LL &x, int b, LL &y) {
if (!b) {x = 1, y = 0;}
else {gcd(b,y,a%b,x);y-=a/b*x;}
}

inline int gcd(int a, int b) {
static LL x,y;
gcd(a,x,b,y);
return (x % MOD + MOD) % MOD;
}

namespace Node_Decomposition{
#define ND Node_Decomposition
const int INF = 1e9;
int tot,node_sz,root,cur;
int sum[N],dep[N],vis[N];
map<int,int> cnt;

void Get_Root(int w, int f) {
sum[w] = 1; int mx = 0;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, node_sz - sum[w]);
if (mx < cur) cur = mx, root = w;
}

void DFS(int w, int f, int delta, LL p, int val) {
cnt[val] += delta;
if (!vis[to[i]] && to[i] != f) {
DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
}
}
}

void cal(int w, int f, int t, LL val) {
vout += cnt[(-val*REV[t]%MOD+MOD)%MOD];
if (!vis[to[i]] && to[i] != f) {
cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
}
}
}

void solve(int w, int sz) {
vis[w] = 1; cnt.clear();
if (!vis[to[i]]) {
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
vout += cnt[0]; cnt[0]++;
if (!vis[to[i]]) {
DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
cal(to[i], w, 1, cost[i] % MOD);
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
if (!vis[to[i]]) {
node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
cur = INF; Get_Root(to[i], w);
solve(root, node_sz);
}
}
}

inline void solve() {
cur = INF; node_sz = n;
Get_Root(1,1);
solve(root,n);
}
};

int main() {
for (int i=1,u,v,w;i<n;i++) {
Add_Edge(u + 1, v + 1, w);
}
REV[0] = 1; REV[1] = gcd(10, MOD);
for (int i=2;i<=n;i++)
REV[i] = (LL)REV[i-1] * REV[1] % MOD;
ND::solve();
printf("%lld\n",vout);
return 0;
}


## 【Codeforces 711E】ZS and The Birthday Paradox

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define pow POW
using namespace std;

const LL MOD = 1000003;

char c=getchar(); LL ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

inline LL pow(LL w, LL t) {
LL ret = 1;
while (t) {
if (t & 1) ret = ret*w % MOD;
w = w*w % MOD; t >>= 1;
}
return ret;
}

inline bool judge(LL n, LL k) {
LL w = 1;
for (int i=1;i<=n;i++) {
w *= 2;
if (w >= k) return false;
} return true;
}

int main(){
if (judge(n,k)) cout<<1<<' '<<1;
else {
LL t1, t2, cnt = (k-1) - __builtin_popcountll(k-1), gcd = pow(pow(2,cnt),MOD-2);
if (k >= MOD) t1 = 0; else {t1 = 1; for (int i=1;i<k;i++) t1 = t1 * (tn - i) % MOD;}
t2 = pow(pow(2,n),k-1); t2 = t2 * gcd % MOD; t1 = t1 * gcd % MOD; t1 = ((t2 - t1)% MOD + MOD) % MOD;
cout<<t1<<' '<<t2;
}
return 0;
}


ps:如果不知道上面的那个定理，貌似自己推也是可以推出来的？