Codeforces Round #539 div2
D 回文串
题意
输入一个回文串，你现在有一个操作：将字符串切一刀或两刀，左右平移被切下来的部分。
问最少切几刀将其变为令一个回文串？若不可能，特判掉。
题解
猜结论：最坏的情况是2。
证明（构造）： 令len为字符串S长度
首先考虑不可能的情况：每个字符都一样；或者除了中间那个字符，其它都一样（len为奇数）。
从这一点出发，我们可以构造出一种切两刀就必定得到不同回文串的方法：
从S的头出发，while(s[i]==s[i-1])i++; 找到第一个不同字符为止，切一刀得到一个prefix,对称地在尾部切一刀得到suffix，交换prefix,suffix 即可。
以上给出最坏的情况是2的构造方法，然后我们只要考虑是否有1的解。
此时问题等价于 “字符环 ”上任意起点是否有不同的回文串。O(N*N)可解。
代码（very tricky)
//O(n)
#include <bits/stdc++.h>
using namespace std;
int solveOdd(const string& s) {//odd
return 2;
}
int solveEven(const string& s) {// ???貌似利用了回文环很强的性质
if (s.length() % 2 == 1) {
return 2;
}
string lf = s.substr(0, s.length() / 2);
string rg = s.substr(s.length() / 2, s.length() / 2);
if (lf != rg) return 1;
return solveEven(lf);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
string s;
cin >> s;
if (s.length() < 3) {
cout << "Impossible" << endl;
return 0;
}
vector<int> cnt(255);//skip init, use stl func
for(char c : s) {
++cnt[c];
}
if (*max_element(cnt.begin(), cnt.end()) >= s.length() - 1) {//only one impossibility
cout << "Impossible" << endl;
return 0;
}
cout << (s.length() % 2 == 0 ? solveEven(s) : solveOdd(s)) << endl;
return 0;
}
O(N^2)
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(const string& s) {//pass by reference reduce time&&space costs
for(int i = 0; i < s.length(); ++i) {
if (s[i] != s[s.length() - i - 1])
return false;
}
return true;
}
bool solve1(string s) {
string t = s;
for(int i = 0; i < s.length(); ++i) {
t = t.back() + t;
t.pop_back(); //more naturally without mod,and make use of string‘s ==
if (s != t && isPalindrome(t)) {
return true;
}
}
return false;
}
bool anyAnswer(const string& s) {
int nt = 0;
for(int i = 0; i < s.length(); ++i) {
nt += s[i] != s[0];//skip an if..else
}
return nt > 1;
}
int32_t main() {//function programing
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);//accelerate cin
string s;
cin >> s;
if (anyAnswer(s)) {
cout << (solve1(s) ? 1 : 2) << endl;
} else {
cout << "Impossible" << endl;
}
return 0;
}
E treap or 线段树
题意
有一个容器，里面有水
维护两个操作：
1 t s (1≤t≤10^9, −109),增加一个事件：从第t秒开始往里倒水的速度变为s.
2 t (1≤t≤10^9),删除第t秒的事件
然后询问
3 l r v (1≤l≤r≤10^9, 0≤v≤10^9)表示假设容器里有体积为的v水，执行l到r的所有操作，什么时候容器里没有水，如果达不到特判掉。
操作和询问共有1e5个
题解
用treap或线段树维护所有（没被删除的）事件
结点里存(t,s) t is key
每个结点同时维护
tL,tR:子树中最小和最大的时间（左右边界）。
speedR:最大时间（右边界）的速度。
res:执行子树里所有操作后消耗（得到）的水量
mn：执行子树所有操作过程中得到的水量最小值
合并操作：LC，RC为左右儿子
tL=LC.tL, tR=RC.tR, speedR=RC.speedR
mn 和res 一同更新：
mn = 0, res = 0
mn = min(mn, LC.mn)
res += LC.res + LC.speedR * (time - LC.tR)
mn = min(mn, res)
res += speed * (RC.tL - time)
mn = min(mn, res + RC.mn)
res += RC.res
mn = min(mn, res)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//mt19937 gen(time(NULL));
mt19937 gen(200);
struct node {
pair<int, int> f, s;
node *le, *ri;
ll mn, res;
int tl, tr;
node() {
mn = 228;
}
node(int l, int r) {
tl = l; tr = r;
mn = 228;
if (l == r) return;
le = new node(l, (l+r)/2);
ri = new node((l+r)/2+1, r);
}
node (node* a, node* b) {
le = a; ri = b;
tl = le->tl; tr = ri->tr;
if (le->mn == 228) {
res = ri->res;
mn = ri->mn;
f = ri->f;
s = ri->s;
return;
}
if (ri->mn == 228) {
res = le->res;
mn = le->mn;
f = le->f;
s = le->s;
return;
}
f = le->f; s = ri->s;
ll del = 1ll*le->s.second*(ri->f.first-le->s.first);
res = le->res+del+ri->res;
mn = min(le->mn, le->res+del);
mn = min(mn, ri->mn+le->res+del);
}
void combine() {
node tmp(le, ri);
*this = tmp;
}
void update(int id, int time, int speed) {
if (tl == tr) {
mn = res = 0;
f.first = s.first = time;
f.second = s.second = speed;
return;
}
if (id <= (tl+tr)/2)
le->update(id, time, speed);
else
ri->update(id, time, speed);
combine();
}
void del(int id) {
if (tl == tr) {
mn = 228;
return;
}
if (id <= (tl+tr)/2)
le->del(id);
else
ri->del(id);
combine();
}
node* get_seg(int l, int r) {
if (tr < l || r < tl) return new node();
if (l <= tl && tr <= r) {
return this;;
}
return new node(le->get_seg(l, r), ri->get_seg(l, r));
}
long double simulate(int r, ll v) {
if (mn == 228) return -1;
if (v+mn > 0 && v+res+1ll*s.second*(r-s.first) > 0) return -1;
if (f == s) return s.first-(long double)v/s.second;
if (le->mn == 228) return ri->simulate(r, v);
long double to = le->simulate(le->s.first, v);
if (to != -1) return to;
v += le->res;
ll del = 1ll*le->s.second*((ri->mn==228?r:ri->f.first)-le->s.first);
if (v+del <= 0) return le->s.first-(long double)v/le->s.second;
v += del;
return ri->simulate(r, v);
}
long double query(int l, int r, int rr, ll v) {
node* t = get_seg(l, r);
return t->simulate(rr, v);
}
};
struct query{
int time, speed, start;
int l, r, type;
query() {}
};
vector <int> pos;
vector <query> q;
int main() {
ios_base::sync_with_stdio(false);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
cout.precision(7);
int qq; cin >> qq;
q.resize(qq);
for (int i = 0; i < qq; ++i) {
cin >> q[i].type;
if (q[i].type == 1) {
cin >> q[i].time >> q[i].speed;
pos.push_back(q[i].time);
}
if (q[i].type == 2) {
cin >> q[i].time;
}
if (q[i].type == 3) {
cin >> q[i].l >> q[i].r >> q[i].start;
}
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
if (pos.size() == 0) pos.push_back(0);
node* t = new node(0, pos.size()-1);
for (int i = 0; i < qq; ++i) {
if (q[i].type == 1) {
int id = lower_bound(pos.begin(), pos.end(), q[i].time)-pos.begin();
t->update(id, q[i].time, q[i].speed);
}
if (q[i].type == 2) {
int id = lower_bound(pos.begin(), pos.end(), q[i].time)-pos.begin();
t->del(id);
}
if (q[i].type == 3) {
int l = lower_bound(pos.begin(), pos.end(), q[i].l)-pos.begin();
int r = --upper_bound(pos.begin(), pos.end(), q[i].r)-pos.begin();
if (q[i].start == 0)
cout << fixed << q[i].l << '\n';
else
cout << fixed << t->query(l, r, q[i].r, q[i].start) << '\n';
}
}
return 0;
}
F 隔板法+Cayley's formula
题意
给你n,m,a,b 表示n个结点的树，结点1..n标号，最大边权为m。a,b为被选定的两个结点问有几棵a,b之间距离为m的树？
题解
首先考虑a,b这条路径的数量，令edges为a,b之间的边数，边权的方案数可以由隔板法得出：选edges条边，使得它们和为m，方法数为C(m-1,edges-1). 结点的方案数由n-2个点选edges-1个的排列得出A(n-2,edges-1).
接下来考虑剩下的结点的方案数，首先，带权边的组合数是m^(n-edges-1)，
然后对于点，我们有一个定理（证明貌似是矩阵之类的）：
综上所述，如果我们把a,b这条链拆开，就得到了edges+1个结点，每个结点作为一个联通分量，那么有T(n,edges+1)种森林，然后把链重新连起来，C(m-1,edges-1)*A(n-2,edges-1) 种方案，最后每个联通分量内部的边赋权值的方案数为m^(n-edges-1)，
所以答案为num[edges]=T(n,edges+1)*C(m-1,edges-1)*A(n-2,edges-1)*m^(n-edges-1).最终对num求和即得答案rep(i,1,n-1)ans+=num[edges];
代码
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
OutputWriter out = new OutputWriter(System.out);
TaskC solver = new TaskC(in, out);
solver.solve();
out.close();
}
static class TaskC {
static int n;
static int m;
static int[] inv;
static int[] fact;
static int[] invfact;
static int[] powN;
static int[] powM;
InputReader in;
OutputWriter out;
TaskC(InputReader in, OutputWriter out) {
this.in = in;
this.out = out;
}
private void solve() {
n = in.readInt();
m = in.readInt();
precalc();
int ans = 0;
int choosePath = 1;
for(int k = 1; k < n; ++k) {
if (k > m) break;
int cur = MathUtil.mul(choosePath, cayley(n, k + 1));
cur = MathUtil.mul(cur, binom(m - 1, k - 1));
cur = MathUtil.mul(cur, powM[n - k - 1]);
choosePath = MathUtil.mul(choosePath, n - k - 1);
ans = MathUtil.sum(ans, cur);
}
out.print(ans);
}
private int cayley(int n, int k) {
if (n - k - 1 < 0) {
return MathUtil.mul(k, MathUtil.binPow(n, MathUtil.mod - 2));
}
return MathUtil.mul(k, powN[n - k - 1]);
}
private int binom(int n, int k) {
return MathUtil.mul(fact[n], MathUtil.mul(invfact[k], invfact[n - k]));
}
private void precalc() {
powN = new int[n + 1];
powM = new int[n + 1];
powN[0] = 1;
powM[0] = 1;
for(int i = 1; i <= n; ++i) {
powN[i] = MathUtil.mul(powN[i - 1], n);
powM[i] = MathUtil.mul(powM[i - 1], m);
}
inv = new int[m + 1];
fact = new int[m + 1];
invfact = new int[m + 1];
inv[0] = inv[1] = 1;
fact[0] = fact[1] = 1;
invfact[0] = invfact[1] = 1;
for(int i = 2; i <= m; ++i) {
inv[i] = MathUtil.mul(inv[MathUtil.mod % i], MathUtil.mod - MathUtil.mod / i);
fact[i] = MathUtil.mul(fact[i - 1], i);
invfact[i] = MathUtil.mul(invfact[i - 1], inv[i]);
}
}
}
static class MathUtil {
private static final int mod = 1_000_000_007;
static int binPow(int a, int n) {
int result = 1;
while (n > 0) {
if (n % 2 == 1) {
result = mul(result, a);
}
n /= 2;
a = mul(a, a);
}
return result;
}
static int mul(int a, int b) {
return (int)((long)a * b % mod);
}
static int sum(int a, int b) {
int result = a + b;
if (result >= mod) result -= mod;
return result;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
writer.println();
}
public void close() {
writer.close();
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private InputReader.SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public double readDouble() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E') {
return res * Math.pow(10, readInt());
}
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E') {
return res * Math.pow(10, readInt());
}
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}
//c++code, one visual studio bug: if you change the fac&&invfac array, the answer will change,in other ide it won't happen.(seems to be address error)
#include<algorithm>
#include<iostream>
#include<sstream>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<math.h>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<ctime>
#include<stack>
#include<map>
#include<set>
#include<list>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define MD(x) x%=mod
//#define x first
//#define y second
typedef double db;
typedef long long ll;
const int MAXN = 30;;
const int maxn = 1e3+2;
const int INF = 1e9;
const db eps = 1e-7;
const int mod = 1e9 + 7;
ll fac[maxn];
ll invfac[maxn];
ll c[maxn];
long long kpow(long long a, long long n) {
long long res = 1;
while (n > 0) {
if (n & 1)res = res * a%mod;
a = a * a%mod;
n >>= 1;
}
return res;
}
void init() {
fac[0] = fac[1] = 1;
invfac[0]=invfac[1] = 1;
rep(i, 2, maxn) {
fac[i] = fac[i - 1] * (ll)i % mod;
invfac[i] = kpow(fac[i], mod - 2);
}
}
ll C(int n, int m) {
if (n < m) return 0ll;
if (m == 0 || n == m) return 1ll;
if (n - 1 == m || m == 1) return n;
return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
ll T(ll n, ll k) {
if (n - k - 1 < 0) {
return k * kpow(n, mod - 2) % mod;
}
return k*kpow(n, n - k - 1)%mod;
}
ll A(int n, int m) {
if (m == 0)return 1;
return fac[n] * invfac[n-m]%mod;
}
int main() {
ll n, m; cin >> n >> m;
init();
ll ans = 0;
rep(i, 1, n - 1)if (i <= m) {
ll tmp = A(n - 2, i - 1);
tmp *= T(n, i + 1); tmp %= mod;
tmp *= C(m - 1, i - 1); tmp %= mod;
tmp *= kpow(m, n - i - 1); tmp %= mod;
ans += tmp; ans %= mod;
}
cout << ans << endl;
cin >> n >> n >> n;
}