模拟|【NOIP模拟】加密+硬币+比特战争
T1：
其实直接转成数组模拟是可过的。。。
正解：
文章图片
代码：
#include
using namespace std;
typedef long long LL;
const int RLEN=1<<18|1;
inline char nc() {
static char ibuf[RLEN],*ib,*ob;
(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob) ? -1 : *ib++;
}
inline LL rd() {
char ch=nc();
LL i=0,f=1;
while(!isdigit(ch)) {if(ch=='-')f=-1;
ch=nc();
}
while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0';
ch=nc();
}
return i*f;
}
inline void W(LL x) {
static int buf[50];
if(!x) {putchar('0');
return;
}
if(x<0) {putchar('-');
x=-x;
}
while(x) {buf[++buf[0]]=x%10;
x/=10;
}
while(buf[0]) {putchar(buf[buf[0]--]+'0');
}
}
const LL mod=1ll<<32;
inline LL exgcd(LL a,LL b,LL &x,LL &y) {b ? (exgcd(b,a%b,y,x),y-=a/b*x) : (x=1,y=0);
}
inline LL cinv(LL t) {
LL x,y;
exgcd(t,mod,x,y);
x=(x%mod+mod)%mod;
return x;
}
inline LL ksc(LL a,LL b,LL rs=0) {for(;
b;
b>>=1,a=(a+a)%mod) if(b&1) rs=(rs+a)%mod;
return rs;
}
int main() {
for(int Q=rd();
Q;
Q--) {
LL t=rd();
t=ksc(t,cinv((1ll<<16)+1));
LL x1=t>>22, x2=(t>>11)^(x1<<11), x3=t^(x1<<22)^(x2<<11);
x2=x2^x1;
x3=x3^x2;
t=(x1<<22)^(x2<<11)^x3;
t=ksc(t,cinv((1ll<<3)+1));
x1=t>>30, x2=(t>>24)^(x1<<6), x3=(t>>18)^(x1<<12)^(x2<<6);
LL x4=(t>>12)^(x1<<18)^(x2<<12)^(x3<<6), x5=(t>>6)^(x1<<24)^(x2<<18)^(x3<<12)^(x4<<6),
x6=t^(x1<<30)^(x2<<24)^(x3<<18)^(x4<<12)^(x5<<6);
x2^=x1;
x3^=x2;
x4^=x3;
x5^=x4;
x6^=x5;
t=(x1<<30)^(x2<<24)^(x3<<18)^(x4<<12)^(x5<<6)^x6;
t=ksc(t,cinv((1ll<<10)+1));
W(t);
putchar('\n');
}
} T2:
DP+矩阵快速幂。
有点难理解（主要是本身太菜了）。
【模拟|【NOIP模拟】加密+硬币+比特战争】令
文章图片
表示凑成
文章图片
的方案数，这样最后的
文章图片
就可以贪心的从大到小由加法原理求得。
考虑如何求得
文章图片
。
由于满足倍数关系，那么就有：
文章图片
感性理解一下就是乘法原理分
文章图片
步求和得到的，每步的的方案数为
文章图片
。
PS：取模是真的慢，建议以后都用代码中的写法，能不取就不取。
代码：
#include
#define int long long
using namespace std;
const int Max=55;
const int mod=1e9+7;
int n,w,num[Max];
inline int add(int a,int b){return (a+b)>=mod?(a+b)%mod:a+b;
}
inline int mul(int a,int b){return (a*b)>=mod?(a*b)%mod:a*b;
}
struct matrix{
int a[Max][Max];
matrix(int t=0){
memset(a,0,sizeof(a));
for(int i=1;
i<=n;
i++) a[i][i]=t;
}
friend inline matrix operator +(const matrix &a,const matrix &b){
matrix c(0);
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=n;
j++)
c.a[i][j]=add(a.a[i][j],b.a[i][j]);
return c;
}
friend inline matrix operator *(const matrix &a,const matrix &b){
matrix c(0);
for(int i=1;
i<=n;
i++)
for(int k=1;
k<=n;
k++)
for(int j=1;
j<=n;
j++)
c.a[i][j]=add(c.a[i][j],mul(a.a[i][k],b.a[k][j]));
return c;
}
friend inline matrix operator ^(matrix a,int b){
matrix c(1);
while(b)
{
if(b&1) c=c*a;
b>>=1,a=a*a;
}
return c;
}
}A[Max];
inline int get_int()
{
int x=0;
char c;
for(c=getchar();
(!isdigit(c));
c=getchar());
for(;
isdigit(c);
c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}inline void init(int p)
{
for(int i=1;
i<=p;
i++) A[p].a[p][i]=1;
if(p>1) A[p]=A[p]+(A[p-1]^(num[p]/num[p-1]));
}signed main()
{
n=get_int(),w=get_int();
for(int i=1;
i<=n;
i++) num[i]=get_int();
for(int i=1;
i<=n;
i++) init(i);
matrix B(0);
for(int i=1;
i<=n;
i++) B.a[1][i]=1;
for(int i=n;
i>=1;
i--)
{
if(w T3:
可证得最优解一定是最小生成树形成过程中的某个状态，于是就显然了。
具体步骤就是做最小生成树，考虑两个联通快，比较合并与不合并即可。
代码：
#include
using namespace std;
const int Max=100010;
int n,m;
long long ans=1e18,sum,f[Max];
int fa[Max],num[Max],mn[Max],mx[Max],u[Max],v[Max],s[Max];
struct shu{int u,v,s;
}edge[Max<<1];
inline int get_int()
{
int x=0;
char c;
for(c=getchar();
(!isdigit(c));
c=getchar());
for(;
isdigit(c);
c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
inline int min(int a,int b){return a
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长