T1
是个我没发现的规律或者叫性质之类的东西，对于任意一个人，你给他现有的芝麻${ imes}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 ",min(n,mod-n)); 23 return 0; 24 }
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{ imes}a_y=k$
${Rightarrow}a_x-k=n{ imes}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 ",ans); 40 return 0; 41 }
T3
有时间晚上会填坑，先咕了
本来以为要各种$ex$家族数学乱搞，结果dp推式子就可过
设$dp[i][j]$代表第$i$层用了$j$种颜色的方案数，这$j$种只要是$j$种就行，不限定是哪$j$种
设$s[i]$代表把第$i$层铺满之后的总方案数，$s[i]=sumlimits_{j=1}^{a[i]}dp[i][j]$
设$f[i][j]$代表用$j$种颜色恰好填满$i$个格子的方案数，$f[i][j]=f[i-1][j-1]{ imes}j+f[i-1][j]{ imes}(j-1)$，如果你用了$j-1$个颜色，那么当前你要开一个新的颜色，由于这个$f$数组，不规定是哪$j$种颜色，所以那另外的一种颜色有$j$种可能，所以${ imes}j$，而如果你不新开一种颜色，由于题目要求可知，相邻位置颜色不能相同，所以${ imes}(j-1)$
设$g[i][j]$代表用$j$种颜色恰好填满$i$个格子，只不过这$j$种颜色是指定的，这样的话$g[i][j]=g[i-1][j-1]{ imes}(m-(j-1))+g[i-1][j]{ imes}(j-1)$，如果新开一种颜色，只剩下$m-j+1$种选择，如果用之前的颜色，就同上，不跟前一个重复就好
关于指定这个问题，我们可以这么理解，$dp$和$f$数组自带组合数，然而$g$数组不够高级，所以他无法拥有组合数，这样的话我们的$dp[i][j]=s[i-1]{ imes}f[a[i]][j]-dp[i-1][j]{ imes}g[a[i]][j]$，我们来理解一下，如果没有第二个限制，那么方案数就是到上一层位置所有的方案数乘上带组合数的$f$，那么不符合第二个条件的要怎么干掉呢，这时候就用到$g$数组了，很明显$dp[i-1][j]{ imes}g[a[i]][j]$就是当前层和上一层所选集合相同的方案数，因为$g$数组里制定了$j$种颜色，而$dp$数组又自带组合数，所以是对的
这样的话这道题就可以$dp$乱搞做下来了，关于那么需要数学乱搞求组合数的做法，指路DeepinC
1 #include<iostream> 2 #include<cstdio> 3 #define maxa 6010 4 #define maxn 1001000 5 #define int long long 6 using namespace std; 7 int n,m,p,maxx; 8 int a[maxn]; 9 int dp[maxa],s[maxn],f[maxa][maxa],g[maxa][maxa]; 10 main() 11 { 12 scanf("%lld%lld%lld",&n,&m,&p); 13 for(int i=1;i<=n;++i) {scanf("%lld",&a[i]); maxx=max(maxx,a[i]);} 14 f[0][0]=1ll; g[0][0]=1ll; s[0]=1ll; 15 for(int i=1;i<=maxx;++i) 16 for(int j=1;j<=i;++j) 17 { 18 f[i][j]=((f[i-1][j]*(j-1))%p+(f[i-1][j-1]*j)%p)%p; 19 g[i][j]=((g[i-1][j]*(j-1))%p+(g[i-1][j-1]*(m-j+1))%p)%p; 20 } 21 for(int i=1;i<=n;++i) 22 for(int j=1;j<=a[i]&&j<=m;++j) 23 { 24 if(j<=a[i-1]) dp[j]=((s[i-1]*g[a[i]][j])%p-(dp[j]%p*f[a[i]][j]%p)%p+p)%p; 25 else dp[j]=(s[i-1]*g[a[i]][j])%p; 26 dp[j]=(dp[j]%p+p)%p; s[i]=(s[i]+dp[j])%p; s[i]=(s[i]%p+p)%p; 27 } 28 s[n]=(s[n]%p+p)%p; printf("%lld ",s[n]); 29 return 0; 30 }