USACO 2020 US Open Platinum

发表于 分类于

USACO 2020 US Open Platinum部分题解。

Sprinklers 2: Return of the Alfalfa

题目链接

loj

题解

显然被C覆盖的点是及其有规律的，是被一条从左上到右下，只会往下和右走的折线切成两半，左下方的部分全覆盖给C。

那么就可以根据这个轮廓线进行DP了，设 $f_{i,j,0/1}$ 表示考虑到第 $i$ 行第 $j$ 列，是在向下走还是向右走，且这个位置填C的方案数。

那么转移分两类讨论一下即可。

时间复杂度 $O(n^3)$。

然后发现这是一个前缀和，那么就是 $O(n^2)$ 的了。

细节初始化什么的注意一下。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll mod=1e9+7;
const ll inv2=(mod+1)>>1;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y){y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;return ans;}
const int N=2005;
int n;
char s[N][N];
ll a[N][N],b[N][N],sa[N][N],sb[N][N];

int main()
{
    FO(sprinklers2);
    scanf("%d",&n);
    fo(i,1,n) scanf("%s",s[i]+1);
    fo(i,2,n+1) if(s[i-1][1]=='.') sb[i][0]=b[i][0]=inv2;
    fo(i,1,n) if(s[1][i]=='.') sa[1][i]=a[1][i]=inv2;
    fo(i,2,n+1)
        fo(j,1,n)
        {
            if(s[i][j]=='.') a[i][j]=Mul(inv2,sb[i][j-1]);
            if(j!=n&&s[i-1][j+1]=='.') b[i][j]=Mul(inv2,sa[i-1][j]);
            sa[i][j]=Add(sa[i-1][j],a[i][j]);
            sb[i][j]=Add(sb[i][j-1],b[i][j]);
        }
    ll sum=1;
    fo(i,1,n) fo(j,1,n) if(s[i][j]=='.') sum=Mul(sum,2);
    sum=Mul(sum,Add(sb[n+1][n],sa[n][n]));
    printf("%lld",sum);
    return 0;
}

Exercise

题目链接

loj

题解

似乎有 $O(n\log n)$ 的神奇做法。。。

对于一个排列我们求的是所有的环长的LCM，那么考虑对于每个质因数分开来求。

记 $F_{x}(p)$ 表示最大的 $k$ 满足 $p^k|x$。那么对于一个拆分 $(x_1,x_2\cdots x_m)$ 及一个质数 $p$ 而言，$p$ 的次数就是 $\max{F_{x_i}(p)}$。

这个 $\max$ 显然不好求，我们用Min-Max容斥进行转换，得到答案为：

$$\sum_{S\in{1,2\cdots m},S\not =\varnothing}(-1)^{|S|-1}\min{F_{S_i}(p)}$$

然后可以枚举这个min是否大于等于某个值 $k$：

$$\sum_{k=1}^{n}\sum_{S\in{1,2\cdots m},S\not =\varnothing}(-1)^{|S|-1}[\min{F_{S_i}(p)}\geq k]$$

注意，上面的式子显然要从 $k=1$ 开始。

要使得最小值大于等于 $k$，这些环长都必须是 $p^k$ 的倍数。

那么现在就是枚举 $x=p^k$，然后看有多少个这样的集合符合情况。

假设这个集合所对应的排列的大小为 $ix$，符合条件的集合有 $F(i)$ 个，那么我们可以从 $n$ 个数中选出 $ix$ 个数，剩下的 $n-ix$ 个随便连，也就是 $F(i)\binom{n}{ix}(n-ix)!$。

现在来看对于一个 $x$，如何求出这个 $F(i)$。$F(i)$ 的定义为从 $[1,i]$ 中选择 $j$ 个长度均为 $x$ 的倍数，那么贡献就是 $(-1)^{j-1}$ 的贡献和。

考虑枚举长度为 $jx$ 的环有多少个，那么复杂度为 $O(\frac{n^2}{x^2}\log \frac{n}{x})$。

考虑枚举当前最小的点所在的环中有多少个点，那么有：$F(i)=-\sum_{j=1}^iF(j)\binom{ix-1}{jx-1}(jx-1)!$。就可以做到时间复杂度 $O(\frac{n^2}{x^2})$。

总的时间复杂度 $O(\sum_{p^k}\frac{n^2}{(p^{k})^2})\leq O(n^2\sum_{i=1}^n\frac{1}{i^2}=O(n^2\zeta(2)))=O(n^2)$

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
const int N=7505;
ll m1,m2;
inline ll Pow(ll x,int y)
{
    ll ans=1;
    for(;y;y>>=1,x=x*x%m1)
        if(y&1) ans=ans*x%m1;
    return ans;
}

ll fac[N],c[N][N];
int n;
bool bo[N];
int pri[N],cnt,p[N];
inline void init(int n)
{
    fac[0]=1;
    fo(i,1,n) fac[i]=fac[i-1]*i%m2;
    c[0][0]=1;
    fo(i,1,n)
    {
        c[i][0]=1; c[i][i]=1;
        fo(j,1,i-1)
        {
            c[i][j]=c[i-1][j]+c[i-1][j-1];
            c[i][j]>=m2?c[i][j]-=m2:0;
        }
    }
    fo(i,2,n)
    {
        if(!bo[i])
        {
            pri[++cnt]=i;
            for(int j=i;j<=n;j*=i) p[j]=i;
        }
        for(int j=1;j<=cnt&&pri[j]*i<=n;j++)
        {
            bo[pri[j]*i]=1;
            if(i%pri[j]==0) break;
        }
    }
}
ll f[N],sum;
inline ll solve(int x)
{
    sum=0;
    f[0]=m2-1;
    int m=n/x;
    fo(i,1,m)
    {
        f[i]=0;
        fo(j,1,i)
            f[i]=(f[i]-(f[i-j]*c[i*x-1][j*x-1]%m2*fac[j*x-1])%m2+m2)%m2;
    }
    fo(i,1,m) sum=(sum+(f[i]*c[n][i*x]%m2*fac[n-i*x]))%m2;
    return sum;
}
int main()
{
    //FO(exercise);
    n=read(); m1=read(); m2=m1-1;
    init(n);
    ll ans=1;
    fo(i,2,n)
        if(p[i])
            ans=ans*Pow(p[i],solve(i))%m1;
    printf("%lld",ans);
    return 0;
}