image.png
20的20次方太大，要用到__int128
#include<bits/stdc++.h>
using namespace std;
struct node{
__int128 a,b;
}t[30];
inline __int128 read()
{
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(__int128 x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
bool cmp(node x,node y){
return x.b+x.a*y.b<y.b+y.a*x.b;
}
int main(){
__int128 n,x;
n=read();
x=read();
for(int i=1;i<=n;i++){
t[i].a=read();
t[i].b=read();
}
sort(t+1,t+1+n,cmp);
for(int i=1;i<=n;i++){
x=t[i].a*x+t[i].b;
}
write(x);
return 0;
}
组合数问题
先通过打表求出前几项
再利用oeis得出规律 https://oeis.org/A070775
找出公式
image.png
n/=4;
涉及到快速幂，逆元，因为n可能为奇数，存在相减情况，最后结果(ans%mod+mod)%mod;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353;
ll power(ll a,ll b){
ll ans=1%mod;
for(;b;b>>=1){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
}
return ans%mod;
}
int main(){
ll n;
cin>>n;
n/=4;
ll x=power(-4,n);
ll y=power(16,n);
ll x1=((x%mod)*((power(2,mod-2)%mod)%mod))%mod;
ll y1=((y%mod)*((power(4,mod-2)%mod)%mod))%mod;
ll res=(x1+y1)%mod;
cout<<(res%mod+mod)%mod<<endl;
return 0;
}
贪吃蛇
BFS板子
#include<bits/stdc++.h>
using namespace std;
char mp[500][500];
typedef struct node
{
int x;
int y;
int s;//表示这是第几步可以走到
}KK;
int vis[500][500];//标记数组防止走重复
int Next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main(){
KK que[500];//创建队列
int n,m;
cin>>n>>m;
int xs,ys,xe,ye;
cin>>xs>>ys>>xe>>ye;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
int head=0,tail=0;
que[head].x=xs;
que[head].y=ys;
que[head].s=0;
vis[xs][ys]=1;
tail++;
int flag=0;
while(head<tail){
for(int i=0;i<4;i++){
int tx=que[head].x+Next[i][0];
int ty=que[head].y+Next[i][1];
if(tx<1||tx>n||ty<1||ty>m) continue;
if(mp[tx][ty]=='.'&&vis[tx][ty]==0)//如果可以走
{
//入队
que[tail].x=tx;
que[tail].y=ty;
que[tail].s=que[head].s+1;//步数加一
vis[tx][ty]=1;//标记已经走过
tail++;//队尾后移
}
if(tx==xe&&ty==ye)//判断是否走到终点
{
flag=1;
break;
}
}
if(flag==1)
break;
head++;//扩展完毕的点出队
}
if(flag==1)
cout<<que[tail-1].s*100<<endl;
else
cout<<-1<<endl;
return 0;
}
image.png
题目最后都要
image.png
所以因为n,m都比较大，所以可以用到
[(-1)(2n-k) * lucas(2n,k,3)]%3
当k为奇数的时候要特殊处理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fac[10];
ll p=3;
void init(){
fac[0]=1;
for(ll i=1;i<p;i++)
fac[i]=fac[i-1]*i%p;
}
ll power(ll a,ll b,ll mod){
ll ans=1;
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
ll C(ll n,ll m){
if(n<m)
return 0;
return fac[n]*power(fac[m]*fac[n-m],p-2,p)%p;
}
ll lucas(ll n,ll m){
if(m==0)
return 1;
return (C(n%p,m%p)*lucas(n/p,m/p))%p;
}
int main(){
init();
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
ll res=lucas(2*n,k);
if(k&1) res = (3 - res) % 3;
cout<<res<<endl;
}
return 0;
}
