JLCPC15

K - Bracket Sequence¶

#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¶

#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¶

$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} \equiv (x_n + b \times \mathrm{inv}(a-1) \times \mathrm{inv}(x_1 + b\times \mathrm{inv}(a-1))) \pmod{p}$

#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¶

#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;
}