## 【日常小测】最长路径

### 解题报告

1. 任意一个竞赛图一定存在哈密尔顿路径
2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

### Code

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

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

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

int main() {
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
pw[0] = 1;
for (int i = 1; i < n * n; i++) {
pw[i] = (pw[i - 1] << 1) % MOD;
}
C[0][0] = 1;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= n; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
f[0] = g[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = g[i] = pw[i * (i - 1) >> 1];
for (int j = 1; j < i; j++) {
g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
}
}
for (int x = 1; x <= n; x++) {
int ans = 0;
for (int i = 1; i <= x; i++) {
ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
}
printf("%d\n", ans > 0? ans: ans + MOD);
}
return 0;
}


## 【TopCoder SRM714】ParenthesisRemoval

### Code

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

const int N = 3000;
const int MOD = 1000000007;

int n,ans;
char s[N];

class ParenthesisRemoval {
public:
int countWays(string ss) {
n = ss.size();
for (int i=0;i<ss.size();i++) {
s[i] = ss[i];
}
ans = 1;
for (int i=0,pfx=0;i<n;i++) {
if (s[i] == '(') {
++pfx;
} else {
ans = (LL)ans * (pfx--) % MOD;
}
}
return ans;
}
private:
};


## 【BZOJ 4714】旋转排列

### 题目大意

1. 对于$\forall i \in [1,n]$ 都有$a_i \ne i$
2. 存在一个长度为$k$的序列$B$，使得$P_{B_i}=B_{i+1}$且$P_{B_k} = B_1$

### Code

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

const int N = 500009;
const int MOD = 1000000007;

int n,ans,fac[N],rev[N],q[N];

inline int C(int a, int b) {
if (a > b || a < 0) return 0;
else return ((LL)fac[b] * rev[a] % MOD) * rev[b-a] % MOD;
}

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

int main() {
fac[0] = fac[1] = q[2] = q[0] = 1;
for (int i=2;i<N;i++) fac[i] = (LL)fac[i-1] * i % MOD;
rev[N-1] = Pow(fac[N-1], MOD - 2);
for (int i=N-2;~i;i--) rev[i] = rev[i+1] * (i + 1ll) % MOD;
for (int i=3;i<N;i++) q[i] = (i - 1ll) * (q[i-1] + q[i-2]) % MOD;
cin>>n;
for (int k=2,g;g=1,k<=n;k++) {
for (int t=1;t*k<=n;t++) {
g = ((LL)g * C(k-1, t*k-1) % MOD) * fac[k-1] % MOD;
ans = (ans + ((t&1)?1:-1) * ((LL)g * C(k*t, n) % MOD) * q[n - k*t]) % MOD;
}
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}


## 【BZOJ 4710】[JSOI2011] 分特产

### Code

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

const int N = 2009;
const int MOD = 1000000007;

int n,m,ans,a[N],C[N][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 cal(int x) {
int ret = C[x][n];
for (int i=1;i<=m;i++) {
ret = (LL)ret * C[n-x-1][a[i]+n-x-1] % MOD;
}
return ret;
}

int main() {
C[0][0] = 1;
for (int i=1;i<N;i++) {
C[0][i] = 1;
for (int j=1;j<N;j++) {
C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
}
}
for (int i=1;i<=m;i++) a[i] = read();
for (int i=0;i<n;i++) {
if (i&1) ans = (ans - cal(i)) % MOD;
else ans = (ans + cal(i)) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}


## 【BZOJ 4735】你的生命已如风中残烛

### Code

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

const int MOD = 998244353;

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 main() {
int n = read(), m = 0, ans = 1;
for (int i=1;i<=n;i++) m += read();
for (int i=2;i<=m;i++) ans = ((LL)ans * ((i!=m-n+1)?i :1)) % MOD;
cout<<ans;
return 0;
}


## 【HDU 4349】Xiao Ming’s Hope

### Code

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

int main() {
for (LL n,ans;~scanf("%I64d",&n);){
ans = pow(2, __builtin_popcountll(n)) + 0.5;
cout<<ans<<endl;
}
return 0;
}


## 【BZOJ 3028】食物

### Code

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

const int MOD = 10007;
const int REV = 1668;

int main() {
int n=0; char pat[600]; cin>>pat+1;
for (int i=1;i<=strlen(pat+1);i++)
n = (n * 10 + pat[i] - '0') % MOD;
cout<<n*(n+1ll)*(n+2)*REV%MOD;
return 0;
}


## 【日常小测】计数

### 一句话题意

$n_1,n_2,n_3,n_4 \le 10^3$

[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A

### Code

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

const int MOD = 1000000007;
const int N = 2009;

int vout,f[N],g[N],C[N][N],PW2[N];

char c=getchar(); int 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 int solve(int a, int b, int c) {
if (a < b) swap(a, b);
if (!a && b) return b == c;
int ret = 0;
for (int i=a-b,j,k;i<=c;++i) {
j = i - a + b; k = c - i - j;
if (j >= 0 && k >= 0 && a >= i + k ) {
(ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD;
}
}
return ret;
}

int main() {
PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD;
C[0][0] = 1; for (int i=1;i<N;i++) {
C[0][i] = 1; for (int j=1;j<=i;j++) {
C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
}
}
if (a + b == 0) f[1] = 1;
else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i);
if (c + d == 0) g[1] = 1;
else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i);
for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD;
printf("%d\n",vout);
return 0;
}


## 【Codeforces 653G】Move by Prime

### Code

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

const int N = 300000+9;
const int L = 22;
const int MOD = 1000000007;

int n,tot,vout,pri[N],vis[N],sur[N],cnt[N][L];
int POW[N],REV[N],sum[N],pre1[N],pre2[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 C(int a, int b) {
if (a > b || a < 0 || b < 0) return 0;
else return ((LL)POW[b] * REV[a] % MOD) * REV[b-a] % MOD;
}

inline int pre_sum(int l, int r) {
if (l > r) return 0;
return (sum[r] - (l?sum[l-1]:0)) % MOD;
}

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

inline void prework() {
n = read(); sur[1] = 1;
for (int i=2;i<N;i++) {
if (!vis[i]) pri[++tot] = i, sur[i] = tot;
for (int j=1;j<=tot&&pri[j]*i<N;j++) {
vis[i*pri[j]] = 1;
sur[i*pri[j]] = j;
if (i % pri[j] == 0) break;
}
}
for (int i=1;i<=tot;i++)
cnt[i][0] = n;

POW[0] = REV[0] = 1;
for (int i=1;i<N;i++)
POW[i] = (LL)POW[i-1] * i % MOD;
REV[N-1] = Pow(POW[N-1], MOD-2);
for (int i=N-2;i;i--)
REV[i] = (LL)REV[i+1] * (i+1) % MOD;
sum[0] = 1;
for (int i=1;i<N;i++)
sum[i] = (sum[i-1] + C(i, n-1)) % MOD;
for (int i=1;i<=n;i++)
pre1[i] = (pre_sum(n-i+1, n-1) - pre_sum(0, n-i-1)) % MOD;
for (int i=1;i<=n;i++)
pre2[i] = (pre2[i-1] + pre1[i]) % MOD;
}

int main() {
prework();
for (int i=1,w;i<=n;i++) {
for (int j=sur[w],tmp;w>1;j=sur[w]) {
for (tmp=0;w%pri[j]==0;tmp++,w/=pri[j]);
cnt[j][tmp]++;
cnt[j][0]--;
}
}
for (int i=1;i<=tot;i++) {
if (cnt[i][0] < n) {
for (int j=0,l=0,r=0;j<L;j++) {
if (cnt[i][j]) {
r += cnt[i][j];
(vout += (LL)(pre2[r] - pre2[l]) * j % MOD) %= MOD;
l = r;
}
}
}
}
printf("%d\n",(vout+MOD)%MOD);
return 0;
}


## 【NOIP十连测】[D3T2] 涂色游戏

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

const int N = 100+9;
const int MOD = 998244353;

int n,m,p,q,POW[N],REV[N],g[N][N];
struct Matrix{
int a[N][N];
inline Matrix() {}
inline Matrix(const Matrix &B) {
memcpy(this,&B,sizeof(*this));
}
inline Matrix(int x) {
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++) {
a[i][i] = x;
}
}
inline Matrix operator * (const Matrix &B) {
Matrix ret(0);
for (int j=1;j<=n;j++) {
for (int i=1;i<=n;i++) {
for (int k=1;k<=n;k++) {
ret.a[i][j] += (LL)a[k][j] * B.a[i][k] % MOD;
ret.a[i][j] %= MOD;
}
}
}
return ret;
}
inline Matrix operator ^ (int t) {
Matrix ret(1),tmp(*this);
while (t) {
if (t & 1) ret = ret * tmp;
tmp = tmp * tmp; t >>= 1;
}
return ret;
}
}trans,ans;

char c=getchar(); int 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 int pow(int w, int t) {
int ret = 1;
while (t) {
if (t&1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t >>= 1;
}
return ret;
}

inline int alph(int a, int b, int x) {
if (x > a || x > b || p-a-b+x < 0) return 0;
int ret = (LL)POW[a] * POW[p-a] % MOD;
ret = (LL)ret * REV[x] % MOD;
ret = (LL)ret * REV[a-x] % MOD;
ret = (LL)ret * REV[b-x] % MOD;
ret = (LL)ret * REV[p-a-b+x] % MOD;
return ret;
}

int main(){
POW[0] = REV[0] = 1;
for (int i=1;i<=max(n,p);i++) {
POW[i] = (LL)POW[i-1] * i % MOD;
}
REV[max(n,p)] = pow(POW[max(n,p)],MOD-2);
for (int i=max(n,p)-1;i;i--) {
REV[i] = (LL)REV[i+1] * (i+1) % MOD;
}
g[1][1] = p;
for (int i=2;i<=n;i++) {
for (int j=1;j<=p;j++) {
g[i][j] = (LL)g[i-1][j-1] * (p - j + 1) % MOD + (LL)g[i-1][j] * j % MOD;
g[i][j] %= MOD;
}
}
for (int a=1;a<=n;a++) {
for (int b=1;b<=n;b++) {
if (a > p || b > p) continue;
for (int x=0;x<=a+b-q;x++) {
trans.a[b][a] += alph(a,b,x);
trans.a[b][a] %= MOD;
}
trans.a[b][a] = ((LL)g[n][b]*REV[p]%MOD) * trans.a[b][a] % MOD;
trans.a[b][a] = ((LL)POW[b]*POW[p-b]%MOD) * trans.a[b][a] % MOD;
}
}
for (int i=1;i<=min(n,p);i++) {
ans.a[i][1] = g[n][i];
}
trans = trans ^ (m-1);
ans = ans * trans;
int vout = 0;
for (int i=1;i<=n;i++) {
vout += ans.a[i][1];
vout %= MOD;
}
printf("%d\n",vout);
return 0;
}


## 【BZOJ 4517】[SDOI2016] 排列计数

$$\begin{array}{l} f(n) = n! – C_n^1 \cdot (n – 1)! + C_n^2 \cdot (n – 2)! – \cdots – C_n^n \cdot 1!\\ f(n) = \frac{{n!}}{{2!}} – \cdots – \frac{{n!}}{{n!}}\\ f(n) = n! \cdot \sum\limits_{i = 2}^n {\frac{{{{( – 1)}^i}}}{{i!}}} \\ f(n) = f(n – 1) \cdot \frac{{n!}}{{(n – 1)!}} + {( – 1)^n} \end{array}$$

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

const int N = 1000000+9;
const int MX = 1000000;
const int MOD = 1000000007;

int p[N],d[N],REV[N];

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

inline LL C(int a, int b) {
return (((LL)p[a]*REV[b])%MOD)*REV[a-b] % MOD;
}

char c=getchar(); int 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;
}

int main(){
p[1] = p[0] = REV[0] = 1; d[1] = 0; d[0] = 1;
for (int i=2;i<=MX;i++) p[i] = (LL)p[i-1]*i % MOD;
REV[MX] = pow(p[MX],MOD-2);
for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1]*(i+1) % MOD;
for (int i=2;i<=MX;i++) d[i] = ((d[i-1] + (i&1?-REV[i]:REV[i])) % MOD + MOD) % MOD;
for (int i=0;i<=MX;i++) d[i] = (LL)d[i]*p[i] % MOD;
if (m > n) puts("0");
else cout<<C(n,m)*d[n-m]%MOD<<endl;
} return 0;
}


## 【UOJ 137】[UER #3] 开学前的日历

70分算法的关键：$$\left( \begin{array}{l} x\\ y \end{array} \right) = \left( \begin{array}{l} x – 1\\ y \end{array} \right) + \left( \begin{array}{l} x – 1\\ y – 1 \end{array} \right)$$

100分的关键：

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

const int N = 300+9;
const int MOD = 998244353;

int f[N][N][N*2],n,m,q,X;

X = (100000005*(LL)X+20150823) % MOD;
return X / 100;
}

int main(){
cin>>m>>n>>q>>X;
for (int i=1,u,v,k;i<=q;i++) {
f[u][v][k]++;
}
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
for (int k=0;k<=n+m;k++) (f[i][j][k] += (f[i-1][j][k+1] + f[i][j-1][k+1]) % MOD) %= MOD;
(f[i][j][0] += (f[i-1][j][0] + f[i][j-1][0]) % MOD) %= MOD;
}
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++)
printf("%d%c",f[i][j][0],(i==n?'\n':' '));
return 0;
}


## 【UOJ 241】破坏发射台

ps：为什么我做这题的时候老想着数位DP

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define S(x,y) ((x)*3+(y)+1)
using namespace std;

const int MOD = 998244353;
const int N = 100000;
const int M = 9;

int n,m,vout;

struct Matrix{
int a[M][M];
inline Matrix() {}
inline Matrix(int v) {memset(a,0,sizeof(a));for(int i=1;i<M;i++) a[i][i]=v;}
inline Matrix operator = (const Matrix &B) {memcpy(&(*this),&B,sizeof(a));}
inline Matrix operator * (const Matrix &B) {
Matrix ret(0);
for (int i=1;i<M;i++) for (int j=1;j<M;j++) for (int k=1;k<M;k++)
ret.a[i][j] = ((LL)a[k][j]*B.a[i][k] + ret.a[i][j]) % MOD;
return ret;
}
inline Matrix operator ^ (int t) {
Matrix ret(1),w=*this;
while (t) {
if (t & 1) ret = ret*w;
w = w*w; t >>= 1;
}
return ret;
}
};

char c=getchar(); int 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 int pow(int w, int t){
int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret*w % MOD;
w = (LL)w*w % MOD; t >>= 1;
}
return ret;
}

int main(){
if (n%2 == 0) {
Matrix ori(0),tra(0); ori.a[S(1,2)][1]=1;
if (m > 3) tra.a[S(0,0)][S(1,2)] = tra.a[S(0,0)][S(2,1)] = (LL)(m - 2) * (m - 3) % MOD;
if (m > 3) tra.a[S(0,0)][S(1,0)] = tra.a[S(0,0)][S(0,1)] = (LL)(m - 3) * (m - 3) % MOD;
if (m > 3) tra.a[S(0,0)][S(2,0)] = tra.a[S(0,0)][S(0,2)] = (LL)(m - 3) * (m - 3) % MOD;
if (m > 3) tra.a[S(0,0)][S(0,0)] = ((LL)(m-4) * (m-4) + m - 3) % MOD;

if (m > 2) tra.a[S(1,0)][S(2,1)] = tra.a[S(0,1)][S(1,2)] = m - 2;
if (m > 2) tra.a[S(1,0)][S(0,1)] = tra.a[S(0,1)][S(1,0)] = m - 2;
if (m > 2) tra.a[S(1,0)][S(0,2)] = tra.a[S(0,1)][S(2,0)] = m - 2;
if (m > 3) tra.a[S(1,0)][S(2,0)] = tra.a[S(0,1)][S(0,2)] = m - 3;
if (m > 3) tra.a[S(1,0)][S(0,0)] = tra.a[S(0,1)][S(0,0)] = m - 3;

if (m > 2) tra.a[S(2,0)][S(1,2)] = tra.a[S(0,2)][S(2,1)] = m - 2;
if (m > 2) tra.a[S(2,0)][S(0,2)] = tra.a[S(0,2)][S(2,0)] = m - 2;
if (m > 2) tra.a[S(2,0)][S(0,1)] = tra.a[S(0,2)][S(1,0)] = m - 2;
if (m > 3) tra.a[S(2,0)][S(1,0)] = tra.a[S(0,2)][S(0,1)] = m - 3;
if (m > 3) tra.a[S(2,0)][S(0,0)] = tra.a[S(0,2)][S(0,0)] = m - 3;

tra.a[S(1,2)][S(0,1)] = tra.a[S(2,1)][S(1,0)] = 1;
tra.a[S(1,2)][S(2,0)] = tra.a[S(2,1)][S(0,2)] = 1;
tra.a[S(1,2)][S(2,1)] = tra.a[S(2,1)][S(1,2)] = 1;
tra.a[S(1,2)][S(0,0)] = tra.a[S(2,1)][S(0,0)] = 1;

tra = tra^(n/2-1); ori = ori * tra;
vout = ((LL)ori.a[S(0,2)][1] + ori.a[S(1,0)][1] + ori.a[S(1,2)][1] + ori.a[S(0,0)][1]) % MOD;
vout = ((LL)vout * m % MOD) * (m-1) % MOD;
printf("%d\n",vout);
}
else {
if (n == 3) printf("%d\n",((LL)(pow(m-1,n-1)-(m-1))*m % MOD + MOD) % MOD);
else {
Matrix ori(0); ori.a[1][1] = 1; ori.a[2][1] = m-2;
Matrix tra(0); tra.a[1][2] = 1; tra.a[2][1] = m-1; tra.a[2][2] = m-2;
tra = tra^(n-5); ori = ori * tra; ori.a[1][1] = (LL)ori.a[1][1]*(m-1)%MOD;
vout = (((LL)(m-1)*(m-2)%MOD)*ori.a[2][1]%MOD + (LL)ori.a[1][1]*(m-1)%MOD) % MOD;
vout = (LL)(pow(m-1,n-1)-vout)*m % MOD;
printf("%d\n",(vout+MOD)%MOD);
}
}
return 0;
}


—– UPD 2017.1.12 —–

## 【HDU 3037】Saving Beans

lucas定理 + 插板法

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 100000+9;

int f[MAXN];

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

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

inline int C(int m,int n, int p) {
if (n > m) return 0;
else return (LL)f[m]*quick_pow(f[m-n],p-2,p)*quick_pow(f[n],p-2,p)%p;
}

int lucas(int m, int n, int p) {
if (n == 0) return 1;
else return ((LL)lucas(m/p,n/p,p) * C(m%p,n%p,p)) % p;
}

int main(){
int T = read(); while (T--) {