2024.7.17 【我们必须知道,我们必将知道】
Wednesday 六月十二
//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的题,
也并不是很难
题目解法还是挺新颖的
看来以后要多接触这种新出现的题型,
至少不能听都没听过
然后就是模数写错了调了好久
吃一堑:有模数的题错了先考虑一下模数是不是打错了
//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个不同集
要求每个元素被选择的次数为偶数
思路还是比较麻烦的
首先,考虑有序选择i个集合的方案数,记作f[i]
考虑去掉有序性,就是 f [ i ] i ! \frac{f[i]}{i!} i!f[i]
考虑使用其他方式表达出f[i]
除去空集,共有 2 n − 1 个集合可选 除去空集,共有2^n-1个集合可选 除去空集,共有2n−1个集合可选
则共 A 2 n − 1 i − 1 种可能 则共A_{2^n-1}^{i-1}种可能 则共A2n−1i−1种可能之后考虑去掉空集可能,
不难发现对于这个f[i],
加入空集并不会产生什么影响
则需减去这f[i-1]种可能
A 2 n − 1 i − 1 − f [ i − 1 ] A_{2^n-1}^{i-1}-f[i-1] A2n−1i−1−f[i−1]
5. 考虑去除重复可能
钦定新加入的第i个与前面第j个重复
则剩余的i-2个为合法方案,
枚举可能出现的前i-1个和可能出现重集的 2 n − 1 − ( i − 2 ) 2^n-1-(i-2) 2n−1−(i−2)个集合
则
f [ i ] = A 2 n − 1 i − 1 − f [ i − 1 ] − f [ i − 2 ] ∗ ( i − 1 ) ∗ [ 2 n − 1 − ( i − 2 ) ] f[i] = A_{2^n-1}^{i-1}-f[i-1]-f[i-2]*(i-1)*[2^n-1-(i-2)] f[i]=A2n−1i−1−f[i−1]−f[i−2]∗(i−1)∗[2n−1−(i−2)]
- 得出答案为 f [ m ] / m ! f[m]/m! f[m]/m!
这里记得求逆元
唯一一道在听课时就听懂的题目
//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共 1 1 11 11^{11} 1111种排列方式
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 ∗ 4 ∗ ∗ 3 10 11*4**3^{10} 11∗4∗∗310种可能