[C++知识库]AtCoder Beginner Contest 242

A

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
int main()
{
//	freopen("A.in","r",stdin);
//	freopen(".out","w",stdout);
	double a,b,c,x;
	cin>>a>>b>>c>>x;
	if(x<=a) cout<<"1"<<endl;
	else if(a+1<=x&&x<=b) {
		cout<<(double)(c)/(b-a)<<endl;
	}else cout<<0<<endl;
	
	return 0;
}

B - Minimize Ordering

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
int main()
{
//	freopen("B.in","r",stdin);
//	freopen(".out","w",stdout);
	char s[212345];
	cin>>(s+1);
	int n=strlen(s+1);
	sort(s+1,s+n+1);
	cout<<(s+1);
	
	
	return 0;
}

C - 1111gal password

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (998244353)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
ll f[1123456][10];
int main()
{
//	freopen("C.in","r",stdin);
//	freopen(".out","w",stdout);
	int n=read();
	For(i,9)f[1][i]=1;
	For(i,n-1) {
		For(j,9) {
			upd(f[i+1][j],f[i][j]);
			if(j<9)upd(f[i+1][j+1],f[i][j]);
			if(j>1)upd(f[i+1][j-1],f[i][j]);
		}
	}
	ll ans=0;
	For(j,9) upd(ans,f[n][j]);cout<<ans<<endl;	
	
	return 0;
}

D - ABC Transform

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (998244353)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
char s[112345];
int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>(s+1);
	int n=strlen(s+1);
	int q=read();
	For(i,q) {
		ll t,k;cin>>t>>k;
		ll p=0;
		while(t>0 && k>1) {
			p=p+1+(k%2==0);
			p%=3ll;
			k=(k+1)/2;
			--t;
		}
		if(t>0) p=(p+t%3)%3;
		char cc=((s[k]-'A')+p)%3+'A';
		cout<<cc<<endl;
	}
	
	
	return 0;
}

E - (?x?)

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (998244353)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
char s[1123456];
char s2[1123456];
ll p26[1123456];
int main()
{
//	freopen("E.in","r",stdin);
//	freopen(".out","w",stdout);
	p26[0]=1;
	For(i,1e6) p26[i]=p26[i-1]*26ll%F;
	
	int T=read();
	
	while(T--) {
		ll ans=0;
		int n=read();
		cin>>(s+1);		
		int m=(n+1)/2;
		For(i,m) {
			int p=s[i]-'A';
			upd(ans,mul(p,p26[m-i]));
		}
		For(i,m) s2[i]=s[i];
		Fork(i,m+1,n) s2[i]=s2[n-i+1];
		s2[0]=s2[n+1]=0;
//		cout<<(s2+1)<<endl;
//		cout<<(s+1)<<endl;
		if (strcmp(s2+1,s+1)<=0) upd(ans,1);
		cout<<ans<<endl;
	}
	
	
	return 0;
}

F - Black and White Rooks

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500 points

Problem Statement
在一个$N?M$的矩阵中放$B$个黑石子和$W$个白石子。

要求：
所有石子放在一个格子里
一个格子最多放一个石子。
同行或同列，没有同色石子。

求方案数 modulo 998244353.

同色石子无区别。

Constraints
1≤N,M≤50
1≤B,W≤2500
B+W≤N×M
All values in input are integers.
Input
Input is given from Standard Input in the following format:

N M B W
Output
Print the count modulo 998244353.

Sample Input 1
Copy
2 2 1 1
Sample Output 1
Copy
4

容斥原理：
答案$={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{k=1}^{n?i}{\sum }_{l=1}^{m?j}(?1{)}^{n+m?i?j?k?l}?C(n,i)C(n?i,k)C(m,j)C(m?j,l)C(ij,w)C(kl,b)$

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (998244353)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
#define MAXN (101015)
ll inj[MAXN],jie[MAXN];
inline ll C(int a,int b) {
	return (ll)jie[a]*inj[b]%F*inj[a-b]%F;
}
ll p=F;
inline int pow2(int a,ll b)  //a^b mod p 
{  
    if (b==0) return 1%p;  
    int c=pow2(a,b/2);  
    c=(ll)c*c%p;  
    if (b&1) c=(ll)c*a%p;  
    return c;  
}  
void pre(int n) {
	jie[0]=1;For(i,n) jie[i]=mul(jie[i-1],i);
	inj[0]=inj[1]=1;Fork(i,2,n) inj[i]=(F-(F/i))*inj[F%i]%F;
	For(i,n) inj[i]=mul(inj[i],inj[i-1]);  
} 
ll n,m,b,w;
int main()
{
//	freopen("E.in","r",stdin);
//	freopen(".out","w",stdout);
	pre(101010);
	ll ans=0;
	cin>>n>>m>>b>>w;
	For(i,n) For(j,m) For(k,n-i) For(l,m-j) if(k*l>=b &&i*j>=w){
		ll p=mul(C(n,i),C(m,j));
		p=mul(p,C(n-i,k));
		p=mul(p,C(m-j,l));
		p=mul(p,C(k*l,b));
		p=mul(p,C(i*j,w));
		if((n+m-i-j-k-l)%2) p=sub(0,p);
		upd(ans,p);
	}
	cout<<ans<<endl;
	return 0;
}

G - Range Pairing Query

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXN (1123456+10)
#define MAXM MAXN
int n,m,a[MAXN];
int b[MAXN]={0};
long long Ti2=0;
struct commend
{
	int l,r,no;
	commend(){}
	commend(int _l,int _r,int _no):l(_l),r(_r),no(_no){}
	friend bool operator<(commend a,commend b){return int(a.l/sqrt(n))<int(b.l/sqrt(n))||(int(a.l/sqrt(n))==int(b.l/sqrt(n)))&&a.r<b.r;	}
}p1[MAXM],p2[MAXM];
long long ans[MAXN];
long long gcd(long long a,long long b){if (!b) return a;return gcd(b,a%b);}
int main()
{
//	freopen("bzoj2038.in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d",&n);
	For(i,n) scanf("%d",&a[i]);
	scanf("%d",&m);
	For(i,m) scanf("%d%d",&p1[i].l,&p1[i].r),p1[i].no=i;
	memcpy(p2,p1,sizeof(p1));
	sort(p2+1,p2+1+m);p2[0].l=1,p2[0].r=0;
	For(i,m)
	{
		if (p2[i-1].l<p2[i].l) Fork(j,p2[i-1].l,p2[i].l-1) Ti2-=(long long)b[a[j]]/2,b[a[j]]--,Ti2+=(long long)b[a[j]]/2;
		if (p2[i].l<p2[i-1].l) Fork(j,p2[i].l,p2[i-1].l-1) Ti2-=(long long)b[a[j]]/2,b[a[j]]++,Ti2+=(long long)b[a[j]]/2;
		if (p2[i-1].r<p2[i].r) Fork(j,p2[i-1].r+1,p2[i].r) Ti2-=(long long)b[a[j]]/2,b[a[j]]++,Ti2+=(long long)b[a[j]]/2;
		if (p2[i].r<p2[i-1].r) Fork(j,p2[i].r+1,p2[i-1].r) Ti2-=(long long)b[a[j]]/2,b[a[j]]--,Ti2+=(long long)b[a[j]]/2;
		ans[p2[i].no]=Ti2;
	}
	For(i,m)
		cout<<ans[i]<<endl;
	return 0;
}