T1

是个我没发现的规律或者叫性质之类的东西，对于任意一个人，你给他现有的芝麻${\times}2$再${\%}(n+m)$，就是每次调整之后他所拥有的芝麻量，考虑一下，如果他是手里芝麻比较少的那个人，这么做一定是对的，如果他是手里芝麻比较多的那个人呢？没证出来，手玩的。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #define int long long
 4 #define maxn 100100000
 5 using namespace std;
 6 int n,m,k,mod,mi;
 7 int pd[maxn],bh[maxn];
 8 int ksm(int a,int b)
 9 {
10     int ans=1;
11     while(b)
12     {
13         if(b&1)  ans=(ans*a)%mod;
14         b=b>>1;  a=(a*a)%mod;
15     }
16     return ans;
17 }
18 main()
19 {
20     scanf("%lld%lld%lld",&n,&m,&k);
21     mod=n+m;  mi=ksm(2,k);  n=(n*mi)%mod;
22     printf("%lld\n",min(n,mod-n));
23     return 0;
24 }

View Code

T2

这题也要化式子，题目中要求合法区间中不包含$x<y$且$a_x{\%}a_y=K$的点对，那么我们对于任意$j$，可以找到小于他且离他最近的符合上面那个式子的$i$，这中间就是所有可以做合法的区间，那么现在的问题就是找到这个$i$

暴力

先枚举$j$，从$j$向前扫一遍，找到离他最近的$i$，计算贡献，这当中由于我们需要保证没有符合上面的那个条件的点对，所以每找到一个$i$，都要更新你$j$向前扫的左上界，因为对于这个$j$找到的$i$，应该是和前面找到的所有的$i$取个$min$，这样的话复杂度是$O(n^2)$的，显然水不过去，考虑优化

优化

我们有没有办法可以在不向前扫的情况下就找到每个$j$对应的$i$呢？考虑对于上面的那个式子的转化，保证$x<y$

　 $a_x{\%}a_y=k$

${\Rightarrow}a_x-n{\times}a_y=k$

${\Rightarrow}a_x-k=n{\times}a_y$

这个时候我们发现所有的$a_y$都是$a_x-k$的因数，那我们完全可以用$O(\sqrt{n})$的复杂度筛出$a_x-k$的所有因数，查找这个因数在$j$前面有没有出现过以及出现过的最大位置，就可以直接找到我们想要的$i$

 1 //j<i 分解a[j]-k，找一个下标最小的i
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<vector>
 5 #define maxn 100100
 6 #define int long long
 7 using namespace std;
 8 int n,k,ans,tail;
 9 int a[maxn],bh[maxn];
10 main()
11 {
12     scanf("%lld%lld",&n,&k);  tail=n;
13     for(int i=1;i<=n;++i)  scanf("%lld",&a[i]);
14     for(int i=n;i>=1;--i)//左端点
15     {
16         int base=a[i]-k,right=tail+1/*右端点*/;
17         if(base<0)  continue;
18         if(base==0)
19         {
20             for(int j=i+1;j<=tail;++j)
21                 if(a[j]>a[i])  {right=j;  break;}
22         }
23         for(int j=1;j*j<=base;++j)
24         {
25             if(base%j==0)
26             {
27                 if(j>k&&bh[j]>i)  right=min(right,bh[j]);
28                 if(base/j>k&&bh[base/j]>i)  right=min(right,bh[base/j]);
29             }
30         }
31         if(right!=tail+1)
32         {
33             ans+=(tail-i+1)*(tail-i+2)/2;
34             ans+=-(right-i)*(right-i+1)/2-(tail-right+1);
35         }
36         tail=right-1;  bh[a[i]]=i;
37     }
38     ans+=tail*(tail+1)/2;
39     printf("%lld\n",ans);
40     return 0;
41 }

View Code

T3

有时间晚上会填坑，先咕了