小米 Online Judge 19年2月常规赛题解
小米 Online Judge 19年2月常规赛题解
描述
小爱同学有一个智能密码锁。锁上有九位数字，小爱同学每次会给A,B,C,D,mod,n六个正整数。 题目是这样的：
现在小爱同学想计算出 G(n)G(n) 的值（G(n)为F(n)的前n项积），并用该值作为密码锁的密码。
由于结果过大，所以答案 G(n)%mod
输入
多组数据。每组包含 6 个整数，分别代表 A, B, C, D, mod, n. (1<=A,B,C,D,mod,n<=1000000000)；数据组数不超过 2000.
输出
输出 G(n)%mod 的值。
答案保留 9 位有效数字，不足则补 0.
输入样例
2 2 2 2 1000 3
7 9 3 4 6 5输出样例
000000064
000000003 题解
标程
Carryon 数数字
Carryon 最近迷上了数数字，然后 Starry 给了他一个区间 [l, r][l,r] ,然后提了几个要求，
- 需要将 ll 到 rr 之间的数全部转化成 16 进制，然后连起来。
- 将连起来的数又转化成 10 进制。
- 将最终结果对 15 取模。
数据范围：1 <= l <= r <= 10000000000001<=l<=r<=1000000000000
输入
单组输入 ll 和 rr 的值
输出
输出最终结果。
输入样例
10 14
输出样例
0 提示：10、11、12、13、14的16进制分别是a、b、c、d、e。依次连在一起是abcde，转换成10进制是703710，对15取模为0。
题解：
标程
Logic Gatekeeper
描述
boshi是Rayment的好朋友。
Rayment最近迷上了一个叫Just Shapes & Beats的音游，于是就推荐给了boshi(网易云上也有这个游戏部分音乐的歌单)。可boshi有点着迷于游戏音乐难以集中精神，有时反应慢了半拍，导致他在第二关就挂了一回。忍无可忍的boshi摘下了耳机，他决定用个更科学的方法来通过这一关。
这首歌的名字就叫做Logic Gatekeeper。如果想的话，你也可以一边听歌一边切这道题目。
游戏的不同关卡攻击方式都不一样，但这关的攻击方式比较简单。形式化地来说，攻击可以被具象化为对一个矩阵的攻击，也就是说如果你待在这个矩阵的范围内，你就会受到1的攻击。
游戏界面可以认为是一个n×m的矩阵，而游戏角色恰好占一个方格的位置。boshi会进行不断地进行预测某个子矩阵的攻击概率升高或降低了一定数值，同时为了评估某一个子矩阵的安全性，他也要知道如果他随机待在子矩阵内的一个位置，受到攻击的期望是多少。当然，初始时整个游戏界面任意一个位置的攻击概率为0。
为了避免小数产生的误差，boshi给出的所有的概率都是在模998244353998244353意义下的值，因此你在输出期望的时候也应该对998244353998244353取模。
Rayment听得脑袋都晕了，boshi只好请你来帮他过了这关，不受一点攻击才能拿到S评定。
输入
第一行三个整数n,m,q，含义同题目描述。
接下来q行有两种格式，如下：
-
1 a b c d k，含义是以(a,b)为左下角,(c,d)为右上角的子矩阵的攻击概率均加上k -
2 a b c d，含义是询问以(a,b)为左下角,(c,d)为右上角的子矩阵的攻击期望
数据有梯度，且对于100\%100%的数据保证满足：
输出
对于每一个2操作，输出一行一个整数，表示相应的答案。
输入样例
4 4 3
1 1 1 3 3 4
1 2 3 4 4 5
2 2 2 3 3输出样例
499122183
标程一
#include <algorithm>
#include <cstdio>
#define rg register
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;
const int maxn=1000010,maxm=100010,mod=998244353;
template <typename Tp> inline void getmin(Tp &x,Tp y){if(y<x) x=y;}
template <typename Tp> inline void getmax(Tp &x,Tp y){if(y>x) x=y;}
template <typename Tp> inline void read(Tp &x)
{
x=0;int f=0;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
if(f) x=-x;
}
struct data{
int tp,t,x,y,id,y2;
bool operator < (const data &p){return x<p.x;}
}q[maxm<<2],tmp[maxm<<2];
int n,m,k,tot,qc,top,ans[maxm],res[maxm],id[maxm<<2];
inline int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
struct BIT{
int a[maxn],a2[maxn];
void add(int p,int v)
{
for(int i=p;i<=m;i+=lowbit(i))
a[i]=pls(a[i],v),a2[i]=pls(a2[i],(ll)p*v%mod);
}
int query(int p)
{
int res=0;
for(int i=p;i;i-=lowbit(i)) res=pls(res,dec((ll)(p+1)*a[i]%mod,a2[i]));
return res;
}
}a,b;
int power(int x,int y)
{
int res=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1)
res=(ll)res*x%mod;
return res;
}
void input()
{
int op,x,y,s,t,val;
read(n);read(m);read(k);m++;tot=k<<1;
for(rg int i=1;i<=k;i++)
{
read(op);read(x);read(y);read(s);read(t);
x++;y++;s++;t++;
if(op==1)
{
read(val);
q[(i<<1)-1]=(data){0,i,s,t,val,y};
q[i<<1]=(data){0,i,x-1,t,mod-val,y};
}
else
{
q[(i<<1)-1]=(data){1,i,s,t,++qc,y};
q[i<<1]=(data){2,i,x-1,t,qc,y};
res[qc]=power((ll)(s-x+1)*(t-y+1)%mod,mod-2);
}
}
sort(q+1,q+tot+1);
}
void cdq(const int &l,const int &r)
{
int mid=(l+r)>>1;
if(l<mid) cdq(l,mid);
if(mid+1<r) cdq(mid+1,r);
rg int i=l,j=mid+1;top=0;
while(i<=mid&&j<=r)
{
if(q[i].t<=q[j].t) tmp[++top]=q[i++],id[top]=0;
else tmp[++top]=q[j++],id[top]=1;
}
while(i<=mid) tmp[++top]=q[i++],id[top]=0;
while(j<=r) tmp[++top]=q[j++],id[top]=1;
for(i=1;i<=top;i++)
{
if(id[i])//r
{
if(tmp[i].tp==1)
ans[tmp[i].id]=pls(ans[tmp[i].id],dec(a.query(tmp[i].y),a.query(tmp[i].y2-
1)));
else if(tmp[i].tp==2)
ans[tmp[i].id]=dec(ans[tmp[i].id],dec(a.query(tmp[i].y),a.query(tmp[i].y2-
1)));
else b.add(tmp[i].y2,tmp[i].id),b.add(tmp[i].y+1,mod-tmp[i].id);
}
else{
if(tmp[i].tp==1)
ans[tmp[i].id]=pls(ans[tmp[i].id],
(ll)tmp[i].x*dec(b.query(tmp[i].y),b.query(tmp[i].y2-1))%mod);
else if(tmp[i].tp==2)
ans[tmp[i].id]=dec(ans[tmp[i].id],
(ll)tmp[i].x*dec(b.query(tmp[i].y),b.query(tmp[i].y2-1))%mod);
else a.add(tmp[i].y2,(ll)tmp[i].id*tmp[i].x%mod),a.add(tmp[i].y+1,(ll)(modtmp[
i].id)*tmp[i].x%mod);
}
}
for(i=1;i<=top;i++)
{
if(!tmp[i].tp){
if(id[i]) b.add(tmp[i].y2,mod-tmp[i].id),b.add(tmp[i].y+1,tmp[i].id);
else a.add(tmp[i].y2,mod-(ll)tmp[i].id*tmp[i].x%mod),a.add(tmp[i].y+1,
(ll)tmp[i].id*tmp[i].x%mod);
}
q[l+i-1]=tmp[i];
}
}
int main()
{
input();
cdq(1,tot);
for(rg int i=1;i<=qc;i++) printf("%lld\n",(ll)ans[i]*res[i]%mod);
return 0;
}