JLCPC15
K - Bracket Sequence¶
问由\(K\)种括号组成长度为\(N\)的不同的括号序列一共有多少个。
如果只有一种那么答案是卡特兰数\(\binom{2N}{N} - \binom{2N}{N-1}\)
如果是 K 种，那么其中任何一对括号可以被替换掉，即\(\binom{2N}{N} - \binom{2N}{N-1}\times K^{N}\)
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <cstdio>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef complex<double> CD;
#define MX maxn - 5
#define LS p<<1
#define RS p<<1|1
#define MP(a,b) make_pair((a),(b))
#define rep_(i,a,b) for(int i=(a); i<(b); ++i)
#define for_(i,a,b) for(int i=(a); i<=(b); ++i)
#define dwn_(i,a,b) for(int i=(a); i>=(b); --i)
inline void chkmax(int &x,int y) {if(x<y) x=y;}
inline void chkmin(int &x,int y) {if(x>y) x=y;}
const int maxn = 200005, inf = 0x3f3f3f3f ;
const ll Inf = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-8, PI = acos(-1), e = 2.71828182845904523536, eu = 0.57721566490153286;
const ll P = 1e9 + 7;
int N, M, T, K, RT, cnt ;
vector<int> v[maxn]; //
ll jc[maxn];
ll fpow(int x) {
ll tmp = N; ll bs = x, res = 1;
while(tmp) {
if(tmp & 1) res = res * bs % P;
bs = bs * bs % P;
tmp >>=1;
}
return res;
}
ll inv(ll x) {
ll tmp = P - 2; ll bs = x, res = 1;
while(tmp) {
if(tmp & 1) res = res * bs % P;
bs = bs * bs % P;
tmp >>=1;
}
return res;
}
int main()
{
//ios::sync_with_stdio(false), cin.tie(0);
jc[0] = 1; cin >> N; cin >> K;
for_(i,1,N * 2) jc[i] = jc[i - 1] * i % P;
ll res1 = jc[2 * N] * inv(jc[N]) % P * inv(jc[N]) % P, res2 = jc[2 * N] * inv(jc[N + 1]) % P * inv(jc[N - 1]) % P;
// printf("%lld\n", (res1 - res2 + P ) % P);
printf("%lld", (res1 - res2 + P ) % P * fpow(K) %P);
return 0;
}
//#include<bits/stdc++.h>
//按 Ctrl + Alt + N 编译运行L¶
只需要判断每个字符和串首是否相等就行了
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int t;cin>>t;
while(t--){
string s;
cin>>s;
int sz=s.size();
char c=s[0];
int flg=1;
for(int i=1;i<sz;i++){
if(s[i]!=c){
cout<<2*sz-i<<'\n';flg=0;break;
}
}
if(flg)cout<<sz-1<<'\n';
}
}G - Matrix Repair¶
一个\(01\)矩阵中出现数据丢失（以\(-1\)表示），给出原矩阵各行、各列的异或值，尝试唯一复原原矩阵。
问题实质是一个模线性方程，对于一个缺失值，只有该行和该列只有它一个缺失值才能被求解。
整个问题可以看成一个无向二分图，将行和列看作点，行\(r\)列\(c\)之间有一条边当且仅当\(m[r][c] = -1\)。
拓扑排序的步骤如下：把所有有一个缺失值的行、列的序号入队，之后逐个出队。如果该行/列已被修复（因为在修复行的时候也会修复列），continue，否则修复之，并将其所有所连节点的缺失值数减一。
#include <bits/stdc++.h>
using namespace std;
int mp[1002][1002];
unordered_set<int>r[1002],c[1002];
int row[1002],col[1002];
int cntr[1002],cntc[1002];
queue<int>qr,qc;
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
if(mp[i][j]==-1) {
r[i].insert(j),c[j].insert(i);
cntr[i]++,cntc[j]++;
}
else row[i]^=mp[i][j],col[j]^=mp[i][j];
}
}
for(int i=1,x;i<=n;i++){
cin>>x;row[i]^=x;
if(cntr[i]==1&&cntc[*r[i].begin()]==1){
mp[i][*r[i].begin()]=row[i];cntr[i]--;cntc[*r[i].begin()]--;continue;
}
if(cntr[i]==1){
qr.push(i);
}
}
for(int i=1,x;i<=n;i++){
cin>>x;col[i]^=x;
if(cntc[i]==1){
qc.push(i);
}
}
while(!qr.empty()||!qc.empty()){
while(!qr.empty()){
if(cntr[qr.front()]==0){qr.pop();break;}
int r1=qr.front();
int c1=*r[r1].begin();
cntr[r1]--;cntc[c1]--;
mp[r1][c1]=row[r1],col[c1]^=mp[r1][c1];
r[r1].erase(c1);c[c1].erase(r1);
if(c[c1].size()==1)qc.push(c1);
}
while(!qc.empty()){
if(cntc[qc.front()]==0){qc.pop();break;}
int c1=qc.front();
int r1=*c[c1].begin();
cntc[c1]--;cntr[r1]--;
mp[r1][c1]=col[c1];row[r1]^=mp[r1][c1];
c[c1].erase(r1);r[r1].erase(c1);
if(r[r1].size()==1)qr.push(r1);
}
}
for(int i=1;i<=n;i++){
if(cntc[i]==0&&cntr[i]==0)continue;
cout<<"-1"<<endl;return 0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<mp[i][j]<<' ';
}
cout<<'\n';
}
return 0;
}C¶
题目给出\(a, x_1, b, x_i\)，要求\(x_i\)是否满足\(x_{i+1} \equiv a \times x_i + b\pmod{p}\)。
化成一个等比数列
\[
x_{i+1} + \frac{b}{a-1} = a\times(x_i + \frac{b}{a-1}) \pmod{p}
\]
根据等比数列递推公式可得
\[
x_{i+1} + \frac{b}{a-1} = a^{n-1}\times(x_1 + \frac{b}{a-1}) \pmod{p}
\]
只有\(a^{n-1}\)是未知的，移项
\[
a^{n-1} \equiv (x_n + b \times \mathrm{inv}(a-1) \times \mathrm{inv}(x_1 + b\times \mathrm{inv}(a-1))) \pmod{p}
\]
然后就是一个BSGS。
参考：SDOI 2013 随机数生成器给出\(a, x_1, b, x_i\)，要求得到\(x_{i+1} \equiv a \times x_i + b\pmod{p}\)的最小\(i\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,m,x,x0;
ll poww(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*a%m;
a=a*a%m,b>>=1;
}
return ans;}
unordered_map<ll,ll>pp;
bool bsgs(ll bas,ll k){
ll mm=ceil(sqrt(m));
ll tmp=k%m;
for(int i=0;i<mm;i++){
pp[tmp]=i;
tmp=tmp*bas%m;
}
ll dy=poww(bas,mm);
tmp=1;
for(int i=0;i<=mm;i++){
if(pp.find(tmp)!=pp.end())return 1;
tmp=tmp*dy%m;
}
return 0;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin>>a>>b>>m>>x0>>x;
if(a==0){
if(b==x||x0==x){cout<<"YES"<<endl;return 0;}
else{cout<<"NO"<<endl;return 0;}
}
if(a==1){
if(b!=0||b==0&&x0==x){cout<<"YES"<<endl;return 0;}
else {cout<<"NO"<<endl;return 0;}
}
if(b+x0*(a-1)==0){
if(x==x0){cout<<"YES"<<endl;return 0;}
else {cout<<"NO"<<endl;return 0;}
}
ll k=(m+x-x0)%m*poww((b*poww(a-1,m-2)+x0)%m,m-2)%m;
k++;
k%=m;
bool ans=bsgs(a,k);
if(ans==0)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
return 0;
}H - Visit the Park¶
题意：给定一个带 0 ∼ 9 边权的图和一条路径，询问沿路径经过边的边权形成数字的期望值。
计算每一条边边权的期望值，之后沿路径统计答案即可。
#include <bits/stdc++.h>
using namespace std;
const int N =300010;
typedef long long ll;
const int mod=998244853;
map<pair<int,int>,ll>dig;
map<pair<int,int>,ll>nm;
ll wei[N],a[N];
ll ny(ll b){
ll x=mod-2,ans=1;
while(x){
if(x&1)ans=ans*b%mod;
b=b*b%mod;
x>>=1;
}
return ans;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n,m,k;
cin>>n>>m>>k;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
dig[make_pair(u,v)]+=w;
nm[make_pair(u,v)]++;
dig[make_pair(v,u)]+=w;
nm[make_pair(v,u)]++;
}
ll ans=0;
wei[k]=1;
for(int i=k-1;i>=2;i--){
wei[i]=wei[i+1]*10%mod;
}
for(int i=1;i<=k;i++)cin>>a[i];
for(int i=2;i<=k;i++){
if(nm[make_pair(a[i],a[i-1])]==0){
cout<<"Stupid Msacywy!\n";return 0;
}
else{
ll dg=dig[make_pair(a[i],a[i-1])],nmb=nm[make_pair(a[i],a[i-1])];
ans+=wei[i]*ny(nmb)%mod*dg%mod;
}
}
cout<<ans%mod<<endl;
return 0;
}
最后更新:
2023-01-31