2024.7.17

2024.7.17 【我们必须知道，我们必将知道】

Wednesday 六月十二

P5999 [CEOI2016] kangaroo

//2024.7.17
//by white_ice
//P5999 [CEOI2016] kangaroo
#include<bits/stdc++.h>
using namespace std;
#define itn long long 
#define int long long
constexpr int oo = 4003;
constexpr int mod = 1000000007;

itn n;
int s,t;

itn f[oo][oo];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin >> n >> s >> t;
	f[1][1] = 1;
	for (int i=2;i<=n;i++){
		for (itn j=1;j<=n;j++){
			if (i==s||i==t){
				f[i][j] = (f[i-1][j-1]+f[i-1][j])%mod;
				continue;
			}
			itn res = (i>s)+(i>t);
			f[i][j] += f[i-1][j-1]*(j-res);
			f[i][j] += f[i-1][j+1]*j;
			f[i][j]%=mod;
		}
	}
	cout << f[n][1]%mod;
	return 0;
}

第一次做这种块状DP的题，

也并不是很难

题目解法还是挺新颖的

看来以后要多接触这种新出现的题型，

至少不能听都没听过

然后就是模数写错了调了好久

吃一堑：有模数的题错了先考虑一下模数是不是打错了

P3214 [HNOI2011] 卡农

//2024.7.17
//by white_ice
//P3214 [HNOI2011] 卡农
#include<bits/stdc++.h>
using namespace std;
#define itn long long
#define int long long 
constexpr int oo = 1000006;
constexpr int mod = 100000007;

itn n;
itn m;

itn a[oo];
itn k[oo];
itn f[oo];

itn qpow(itn x,itn b){
    int out=1;
    x%=mod;
    for (;b;b>>=1,(x*=x)%=mod)
        if(b&1)
            (out*=x)%=  mod;
    return out;
}
signed main(){
  //  ios::sync_with_stdio(0);
//    cin.tie(0),cout.tie(0);
    cin >> n >> m ;
    a[0] = 1;
    f[0] = 1;
    f[1] = 0;
    k[0] = 1;
    int sum = 1;
    for (itn i=1;i<=n;i++) sum=(sum*2)%mod;
    //sum -= 1;
    for (int i=1;i<=m;i++) a[i]=a[i-1]*(sum-i+mod)%mod;
    for (itn i=1;i<=m;i++)
        k[i]=k[i-1]*i%mod;
    int g = qpow(k[m],mod-2);
    //cout << g;
    for (itn i=2;i<=m;i++)
        f[i] = ((a[i-1]-f[i-1]+mod)%mod-f[i-2]*(i-1)%mod*(sum-i+1+mod)%mod+mod)%mod;

    cout << (f[m]*g)%mod;
    return 0;
}

题目很简单，

从已有的集合中选出m个不同集

要求每个元素被选择的次数为偶数

思路还是比较麻烦的

1. 首先，考虑有序选择i个集合的方案数，记作f[i]

2. 考虑去掉有序性，就是$\frac{f[i]}{i!}$

3. 考虑使用其他方式表达出f[i]
   $$除去空集，共有2^n-1个集合可选$$
   $$则共A_{2^n-1}^{i-1}种可能$$

4. 之后考虑去掉空集可能，

不难发现对于这个f[i]，

加入空集并不会产生什么影响

则需减去这f[i-1]种可能
$$A_{2^n-1}^{i-1}-f[i-1]$$
5. 考虑去除重复可能

钦定新加入的第i个与前面第j个重复

则剩余的i-2个为合法方案，

枚举可能出现的前i-1个和可能出现重集的$2^n-1-(i-2)$个集合

则
$$f[i]=A_{2^n-1}^{i-1}-f[i-1]-f[i-2]\ast (i-1)\ast [2^n-1-(i-2)]$$

6. 得出答案为$f[m]/m!$

这里记得求逆元

Balanced Subsequences

唯一一道在听课时就听懂的题目

//2024.7.17
//by white_ice
//Balanced Subsequences
#include<bits/stdc++.h>
using namespace std;
#define itn int
constexpr int oo = 4003;
constexpr itn mod = 1000000007;

itn t;
itn n,m,k;
int c[oo][oo];
void getc(){
    for (itn i=0;i<=4000;i++)
        c[i][0] = 1;
    for (itn i=1;i<=4000;i++)
        for (itn j=1;j<=i;j++)
            c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
}


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    getc();

    cin >> t;
while (t--){
    cin >> n >> m >> k;
    if (k>m||k>n){
        cout << 0 << '\n';
        continue;
    }
    cout << (c[n+m][k]+mod-c[n+m][k-1])%mod << '\n';
}
    return 0;
}

关键：找到一个奇妙的小转化

共k对匹配成功，则说明剩余的左右括号，以

$$))))))((((((($$

这种形式存在，

即提供了n+m-*k个空位

插入合法括号序列即可

（我爱博弈！！

给定一个长为十一的排列，
每个数有1~11共$11^{11}$种排列方式
Alice and Bob轮流取数，
Alice取2（大于等于2的数存在），Bob取1
Alice先手，不能操作者输
问共多少种起始局面种先手胜

首先不难发现先手必胜局面一定是总和为3的倍数加2的情况

考虑这些情况即可，

对于一个每个数全为三的倍数的情况，先手必输，因为先手选什么，后手都可以保证维持在三的倍数

取到最后一个数

考虑十个三和一个五的情况，发现先手胜，

不难推出在这种只有一个数是模3余2，其他数是三的倍数时，先手必胜

那么考虑多个数组合，其和为模3余2，

为了不取成1（当存在一时，BOb可以乱取，只要不取1，最后Alice一定无法移动）

这些情况下最后都会成为2，2，3，3。。。。

的情况或存在了1

也就是只有其中一个数为模三余二=，其他数为三的倍数时才有必胜策略

共$11\ast 4\ast \ast 3^{10}$种可能