2018-07-19
本题其实是求,两条不相交,可重和的路径的数量. 同时,起点均为$(n,0)$,终点均为$(0,m)$. 我们可以选择平移01这条路径$->$起点$(n-1, -1)$,终点$(-1, m-1)$. 这就变成了求两条严格不相交路径的数量,然后套用一个神奇怪的定理: $Lindström–Gessel–Viennot lemma$ 首先得到$[a_{1} = (n, 0), a_{2} = (n-1, -1), b_{1} = (0, m), b_{2} = (-1, m-1)]$ 然后得到行列式$[e(a1, b1), e(a1, b2); e(a2, b1), e(a2, b2)]$ $e(u,v)$为 $u$ 到 $v$ 边数之和,显然此题可以用dp来快速求得: $dp[i][j] = dp[i-1][j] + dp[i][j-1]$ $e(u,v) = dp[u.x + v.x][u.y + v.y]$ 此题得解
/* ***********************************************
Author :JiangYu
Created Time :2018年07月19日 星期四 20时09分37秒
File Name :a.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
const int N = 1024;
const int MOD = 1e9 + 7;
void update(int &x, int a) {
x += a;
x %= MOD;
}
int sqr(int x) {
return 1ll * x * x % MOD;
}
int dp[N][N];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
dp[0][0] = 1;
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
if(i) update(dp[i][j], dp[i-1][j]);
if(j) update(dp[i][j], dp[i][j-1]);
}
}
int n, m;
while(scanf("%d%d", &n, &m) != EOF) {
printf("%d\n",int( (sqr(dp[n][m]) + MOD - 1ll * dp[n-1][m+1] * dp[n+1][m-1] % MOD ) % MOD ));
}
return 0;
}
此题感谢 美食不可负064 的题解 参考: B题 解题思路
首先,这道题的表述方法以前出过类似的.将图伪装成一个矩阵,所以可以一眼看出来. 这是一个每个点度数为$2$,没有自环,允许有重边的无向图. 每个点度数均为$2$,画一下可以发现,每一个点属于且仅属于一个环. 所以这是一个有很多个简单环的图. 定义$dp[n]$表示n个点构成的合法图的方案数. 考虑从前面的$n-1$个球中取k个球与新球组成一个环$: C_{n-1, k} * (n-1-k)!$. 由于对称性要除以$2$. 同时,只取一个球时不用考虑对称性$: (n-1)*dp[n-2]$.
最后得$: dp[n] = (n-1)dp[n-2] + sigma(x:2->n-3)((n-1)!/(2*x!)dp[x])$
巧妙的化简为$: dp[n] = (n-1)dp[n-2] + (n-1)dp[n-1] - (n-1)(n-3)dp[n-3]/2$
/* ***********************************************
Author :JiangYu
Created Time :2018年07月20日 星期五 01时09分59秒
File Name :b.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
int mod;
void update(int &x, int a) {
x += a;
x %= mod;
}
const int N = 1e5 + 10;
int dp[N];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
while(scanf("%d%d", &n, &mod) != EOF) {
memset(dp, 0, sizeof dp);
dp[0] = 1;
int sum = 0;
for(int i = 1; i <= n; ++i) {
dp[i] = dp[i-2] * (i - 1ll) % mod;
sum = sum * (i - 1ll) % mod;
if(i >= 3) {
update(sum, (i - 1ll) * (i - 2) / 2 % mod * dp[i -3] % mod);
}
update(dp[i], sum);
}
printf("%d\n", dp[n]);
}
return 0;
}
求G2的子图里有多少个与G1同构,但是有去掉自同构的数量. 我不会算自同构,所以直接$n!$枚举了所有的同构方案,然后用set存下去重.
/* ***********************************************
Author :JiangYu
Created Time :2018年07月19日 星期四 14时19分52秒
File Name :d.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int N = 10;
int n, m1, m2;
int pre[N];
int x1[100], Y1[100], x2[100], y2[100];
bool vis[20][20];
struct Node{
vector<int> V;
vector<P> E;
bool operator<(const Node &o) const {
for(int i = 0; i < (int)V.size(); ++i)
if(V[i] != o.V[i]) return V[i] < o.V[i];
for(int i = 0; i < (int)E.size(); ++i)
if(E[i] != o.E[i]) return E[i] < o.E[i];
return 0;
}
};
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d%d", &n, &m1, &m2) != EOF) {
memset(x1, 0, sizeof x1);
memset(x2, 0, sizeof x2);
memset(Y1, 0, sizeof Y1);
memset(y2, 0, sizeof y2);
memset(vis, 0, sizeof vis);
//cout << n << " " << m1<< " " << m2<< endl;
for(int i = 1; i <= n; ++i)
pre[i] = i;
for(int i = 1; i <= m1; ++i) {
scanf("%d%d", &x1[i], &Y1[i]);
}
for(int i = 1; i <= m2; ++i) {
scanf("%d%d", &x2[i], &y2[i]);
vis[x2[i]][y2[i]] = vis[y2[i]][x2[i]] = 1;
}
set<Node>S;
do{
bool flag = 0;
for(int i = 1; i <= m1; ++i) {
int u = pre[x1[i]], v =pre[Y1[i]];
//cout << u<< " " << v<< endl;
if(vis[u][v] == 0) {
flag = 1;
break;
}
}
if(flag == 0) {
vector<int> V;
for(int i = 1; i<= n; ++i) {
V.push_back(pre[i]);
}
sort(V.begin(), V.end());
vector<P> E;
for(int i = 1; i<= m1; ++i) {
P p(pre[x1[i]], pre[Y1[i]]);
if(p.first > p.second) swap(p.first, p.second);
E.push_back(p);
}
sort(E.begin(), E.end());
S.insert({V,E});
}
else continue;
}while(next_permutation(pre+1, pre+1+n));
printf("%d\n", S.size());
}
return 0;
}
题意为求长度为$n-m$的子序列有几个.有两个很关键的限制条件: 其一,$S_i <= 10$. 所以可以设$dp[i][j]$表示长度为$i$, 结尾为$j$的子序列的数量. 显然只需要$dp[1e5][10]$的空间就足够了.另外,设$sun[i]$表示长度为$i$的子序列数量. 很简单的可以想到,最后的答案为$sum[n-m]$. 同时得到$O(n^2)$的转移方程为:
for(int i = 1; i <= n; ++i) {
for(int j = i; j >= 1; --j) {
sum[j] += (sum[j-1] - dp[j][s[i]])
dp[j][s[i]] = sum[j-1]
/*********************
显然sum[j-1] == dp[j][s[i]],
sum[j] 要加上所有的: 新的sum[j-1] - 旧的dp[j][s[i]]
*********************/
}
}
再考虑第二个关键点$: m \leq 10$.而我们又只需要倒数的m个sum与dp. $O(n^2)$的复杂度立马可以缩减为$O(n*m)$
/* ***********************************************
Author :JiangYu
Created Time :2018年07月20日 星期五 21时26分15秒
File Name :e.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
int MOD = 1e9 + 7;
const int N = 1e5 +10;
const int M = 15;
int s[N];
int dp[N][M], sum[N];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n, m, k;
while(scanf("%d%d%d", &n, &m, &k) != EOF) {
for(int i = 1; i <= n; ++i) {
scanf("%d", &s[i]);
}
memset(dp, 0, sizeof dp);
memset(sum, 0, sizeof sum);
sum[0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = i; j >= 1 && j >= i - m - 1; --j) {
sum[j] += (sum[j-1] - dp[j][s[i]]) % MOD;
sum[j] %= MOD;
dp[j][s[i]] = sum[j-1];
}
}
printf("%d\n", (sum[n-m] + MOD )% MOD);
}
return 0;
}
不是数学玩家,补的很吃力,题解先空缺着吧.
/* ***********************************************
Author :JiangYu
Created Time :2018年07月20日 星期五 22时10分08秒
File Name :f.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
class PolyInter
{
public:
void init(const std::vector<int>& v, int m = 0)
{
mod_ = m, deg = v.size(), val = buf = v;
inv.resize(std::max(2, deg));
inv[1] = 1;
for (int i = 2; i < deg; ++ i) {
inv[i] = 1LL * (mod() - mod() / i) * inv[mod() % i] % mod();
}
}
int eval(long long n)
{
long long b = 1;
for (int i = 1; i < deg; ++ i) {
b = b * residue(n - i + 1) % mod() * inv[i] % mod();
buf[i] = b * val[i] % mod();
}
b = 1;
int result = buf[deg - 1];
for (int i = deg - 2; i >= 0; -- i) {
b = (mod() - b) * inv[deg - 1 - i] % mod() * residue(n - i - 1) % mod();
result += buf[i] * b % mod();
if (result >= mod()) {
result -= mod();
}
}
return result;
}
private:
int mod() const {
return MOD ? MOD : mod_;
}
int residue(long long x) const {
x %= mod();
return x < 0 ? x + mod() : x;
}
int mod_, deg;
std::vector<int> inv, val, buf;
};
void update(int& x, int a)
{
x += a;
if (x >= MOD) {
x -= MOD;
}
}
int pow(int a, int n)
{
int result = 1;
while (n) {
if (n & 1) {
result = 1LL * result * a % MOD;
}
a = 1LL * a * a % MOD;
n >>= 1;
}
return result;
}
const int N = 1024;
int a[N];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
while(scanf("%d", &n) != EOF) {
int prod = 1;
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
prod = 1ll * prod * a[i] % MOD;
}
sort(a, a+n);
int result = prod;
int pre = 1;
for(int i = 0; i < n; ++i) {
int prev = i ? a[i - 1] : 0;
int exp = n - i;
vector<int> vals(exp + 2);
for(int j = 1; j <= exp + 1; ++j) {
vals[j] = vals[j - 1];
update(vals[j], prod);
update(vals[j], MOD - 1ll * pre * pow(j, exp) % MOD);
}
PolyInter p;
p.init(vals);
update(result, p.eval(a[i]));
update(result, MOD - p.eval(prev));
pre = 1ll * pre * a[i] % MOD;
}
printf("%d\n", result);
}
return 0;
}
第一次写斯坦纳树的题,先学了一下模板.这个题有两点不同: 1.要在找最小值的时候统计数量 2.要注意顺序问题,避免重复计数.可以设定1为根,同时合并$sub, sta^sub$时.保证$min{sub} < min{sta^sub}$
/* ***********************************************
Author :JiangYu
Created Time :2018年07月22日 星期日 13时24分38秒
File Name :g.cpp
************************************************ */
#include <bits/stdc++.h>
const int MOD = 1e9 + 7;
using namespace std;
typedef pair<int, int> P;
#define PB push_back
#define ll long long
static const P one {1, 1};
int lowbit(int k) {
return k & -k;
}
P add(const P & a, const P & b) {
return {a.first + b.first, 1ll * a.second * b.second % MOD};
}
void update(P&x, const P &a) {
if(a.first < x.first) {
x = {a.first, 0};
}
if(a.first == x.first) {
x.second += a.second;
x.second %= MOD;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n, m, l;
while(scanf("%d%d%d", &n, &m, &l) != EOF) {
vector< vector<int> > g(n+1);
for(int i = 1; i <= m; ++i) {
int a, b;
scanf("%d%d",&a, &b);
a--;
b--;
g[a].PB(b);
g[b].PB(a);
}
if(l == 1) {
puts("1");
continue;
}
l--;
vector< vector<P> > dp(1<<l, vector<P>(n, P{m+1, 0})),
merged(n, vector<P>(1<<l, P{m+1, 0}));
int root = l;
for(int i = 0; i < l; ++i) {
dp[1<<i][i] = {0, 1};
}
for(int sta = 0; sta < 1<<l; ++sta) {
for(int u = 0; u < n; ++u) {
auto & ref = merged.at(u);
for(int subset = sta; subset > 0; subset = subset - 1 & sta) {
if(lowbit(subset) == lowbit(sta)) {
update(ref.at(sta), add(dp.at(subset).at(u), ref.at(sta ^ subset)));
}
}
}
for(int u = 0; u < n; ++u) {
for(int v : g[u]) {
update(dp.at(sta).at(v), add(merged.at(u).at(sta), one));
}
}
auto & ref = dp.at(sta);
priority_queue<P> pq;
for(int u = 0; u < n; ++u) {
pq.emplace(ref.at(u).first, u);
}
while(!pq.empty()) {
auto top = pq.top();
pq.pop();
int u = top.second;
if(top.first == ref.at(u).first) {
for(int v : g.at(u)) {
P todo = add(ref.at(u), one);
if(todo.first < ref.at(v).first) {
pq.emplace(todo.first, v);
}
update(ref.at(v), todo);
}
}
}
for(int u = 0; u < n; ++u) {
update(merged.at(u).at(sta), dp.at(sta).at(u));
}
}
printf("%d\n", merged.at(root).at((1<<l) - 1).second);
}
return 0;
}
裸莫队会被卡常,但是你多交几次可能就过了. 这种玄妙的做法就不贴代码了=.= 正解是用一个$last[x]$记录$x$元素最后一个位置,$first[x]$记录$x$元素第一个位置. 离线处理,把r从小到大排序处理,计算没出现的数字个数. $BIT$维护
/* ***********************************************
Author :JiangYu
Created Time :2018年07月19日 星期四 23时49分50秒
File Name :j.cpp
************************************************ */
#include <bits/stdc++.h>
const int N = 1e5 + 10;
using namespace std;
int a[N], first[N], last[N];
struct Query{
int l, r, id;
Query(){}
bool operator < (const Query &o) {
return r < o.r;
}
}Q[N];
int ans[N], bit[N];
int lowbit(int k) {
return k & -k;
}
void add(int x, int y) {
while(x > 0) {
bit[x] += y;
x -= lowbit(x);
}
}
int sum(int x) {
int res = 0;
while(x < N) {
res += bit[x];
x += lowbit(x);
}
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n, q;
while(scanf("%d%d", &n, &q) != EOF) {
memset(last, 0, sizeof last);
memset(first, 0, sizeof first);
memset(bit, 0, sizeof bit);
int tot = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
last[a[i]] = i;
if(first[a[i]] == 0)
tot++, first[a[i]] = i;
}
for(int i = 1; i <= q; ++i) {
int l, r;
scanf("%d%d", &l, &r);
Q[i].l = l, Q[i].r = r;
Q[i].id = i;
}
sort(Q+1, Q+1+q);
for(int i = 1, k = 1; i <= n; ++i) {
while(k <= q && Q[k].r == i) {
ans[Q[k].id] = tot;
ans[Q[k].id] -= sum(Q[k].l);
k++;
}
if(last[a[i]] == i) {
add(first[a[i]] - 1, 1);
}
}
for(int i = 1; i <= q; ++i)
printf("%d\n", ans[i]);
}
return 0;
}