Sub-cycle Graph

是时候回顾一波青岛站打铁时没想出来的题了QAQ。

题目传送门:ZOJ4069

求由 n 个点组成 k 条链,形成的所有图的方案数,对 1e9+7 取模。

首先,我们先考虑由 m 个点形成 1 条链的不同方案个数。显然对任意排列,去除倒过来的那个就行了。将方案数记为 l_m,则可以得到

l_m = \begin{cases} 1, & m=1 \\ \frac{m!}{2}, & m>1 \end{cases}

那么似乎接下来就是求它的生成函数了。在这里我们选择它的指数型生成函数。

L(x) = \sum_{m=1}^\infty l_m \frac{x^m}{m!} = \frac{1}{2}\left(2x+x^2+x^3+\cdots\right) = x\left(1-\frac{x}{2}\right)\frac{1}{1-x}

那么现在取 k 条链,我们可以计算出

A_k(x) = \sum_{n=1}^\infty a_{n,k} \frac{x^n}{n!} = \left[L(x)\right]^k = x^k \left(1-\frac{x}{2}\right)^k \left(\frac{1}{1-x}\right)^k

由于这 k 条链之间是不考虑先后关系的,所以

b_{n,k} = \frac{a_{n,k}}{k!}

就是最终的答案。

考虑一下题目是多测的,而且测试样例数高达 T = 2 \times 10^4,是不能进行FFT的。

我们可以发现

\left(1-\frac{x}{2}\right)^k = \sum_{s=0}^k C_k^s \left(-\frac{1}{2}\right)^s x^s

是可以用二项式定理做出来的。

然后考虑一下,后面的 1/(1-x)^k 与前面这项进行卷积,其实就相当于对前面的数列进行了 k 次前缀和。

emmmmm,看到网上有个dalao说

求k次前缀和的第m项,想必现在是个人都应该会了

突然自闭.jpg。然后推了推。假设这个数列原来是

\lbrace x_0, x_1, x_2, \cdots \rbrace

对它进行 k+1 次前缀和,它会变成

\lbrace C_k^k x_0, C_{k+1}^k x_0 + C_k^k x_1, C_{k+2}^k x_0 + C_{k+1}^k x_1 + C_k^k x_2, \cdots \rbrace

即第 n 项为

\sum_{i=0}^n C_{k+i}^k x_{n-i}

单次询问复杂度是 O(m) 的,那么现在可以开始写代码啦!

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
lld fac[MAXN], inv[MAXN], invs[MAXN];

inline void init()
{
    fac[0] = invs[0] = 1;
    fac[1] = inv[1] = invs[1] = 1;

    for (int i = 2; i < MAXN; i++)
    {
        fac[i] = i * fac[i-1] % MOD;
        inv[i] = (MOD-MOD/i) * inv[MOD%i] % MOD;
        invs[i] = inv[i] * invs[i-1] % MOD;
    }
}

inline lld C(int n, int k)
{
    if (n < k) return 0;
    return fac[n] * invs[k] % MOD * invs[n-k] % MOD;
}

void solve()
{
    int n, m, k;
    scanf("%d %d", &n, &m);

    if (m > n)
    {
        printf("0\n");
    }
    else if (m == n)
    {
        printf("%lld\n", fac[n-1]*inv[2]%MOD);
    }
    else
    {
        k = n - m;
        lld ans = 0, inv2s = 1;

        for (int i = m; i >= 0; i--)
        {
            ans += C(k-1+i,i) * C(k, m-i) % MOD * inv2s % MOD;
            inv2s = inv2s * (MOD-inv[2]) % MOD;
        }

        ans = (ans % MOD + MOD) % MOD;
        ans = ans * fac[n] % MOD * invs[k] % MOD;
        printf("%lld\n", ans);
    }
}

int main()
{
    init();
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

Xamarin.Forms 安卓沉浸式状态栏

一开始用MasterDetailPage做DrawerLayout的时候发现没办法透过状态栏,记录踩坑全过程。

values/style.xmlMainTheme.Base 里面加入:

<item name="android:windowTranslucentStatus">true</item>

然后状态栏是透过去了,但是Toolbar也跟着上去了……

values/style.xmlMainTheme 里面加入:

<item name="actionBarSize">@dimen/action_bar_default_height_material_overlay</item>

action_bar_default_height_material_overlay竖屏76.0dip,横屏68.0dip

layout/Toolbar.axml里加入两个属性

<android.support.v7.widget.Toolbar
...
android:layout_height="?attr/actionBarSize"
android:minHeight="?attr/actionBarSize"
android:paddingTop="12dp"
app:titleMarginTop="24dp"
...
/>

大致是完成了。

后期发现ActionMode的状态栏会变宽,后来这样解决

values/style.xml里面加入:

<style name="MainTheme.ActionMode" parent="Widget.AppCompat.ActionMode">
<item name="height">@dimen/action_mode_default_height_material_overlay</item>
<item name="actionBarSize">@dimen/action_mode_default_height_material_overlay</item>
</style>

values/style.xmlMainTheme.Base里面加入:

<item name="actionModeStyle">@style/MainTheme.ActionMode</item>

action_mode_default_height_material_overlay竖屏56.0dip,横屏48.0dip

业界毒瘤(误)OpenLitespeed

:confused: 前段时间发现伪静态设置一直都不对,后来发现OLS根本没有读取伪静态规则,后台INFO级别没有记录任何。先挂在这里。

但是突然又莫名其妙可以伪静态了,可能是要把日志级别调整为9。后来发现要restart才行,reload还是没有用的。

–2017/7/17更新–

再带点今晚读OLS的admin网站源码的感受吧。

OLS的配置文件是一种很奇特的格式,

继续阅读“业界毒瘤(误)OpenLitespeed”