无题8

题解：

第一题：开始想找循环节，但数据很好卡； 后来想小的一直拿，那么另一个就会出现负数，抵消+打表发现就是2^k在mod(n+m)的值；

#include
using namespace std;
#define ll long long
ll mod, n, m;ll ksm(ll a, ll b){ll ret = 1;for(; b; b >>= 1, a=a*a%mod)if(b&1) ret=ret*a%mod;return ret;
}int main(){freopen("sesame.in","r",stdin);freopen("sesame.out","w",stdout);ll k;cin>>n>>m>>k;mod = n + m;if(n > m) swap(n, m);ll ans = ksm(2, k);n = ans * n % mod;cout<endl;
} 

 

第二题：,Ax % Ay = k ==>  Ax - k = n * Ay; 只需要判断（Ax - k）是否整除Ay即可，

ai <= 1e5; 利用这个性质想到拆分, 把Ax的因子都分解出来，如果他包含Ay,就记录一个max(now, lst),往后扫；

O（n√n）

#include
using namespace std;const int M = 1e5 + 10;
#define ll long long
int lst[M], a[M], k;
void divi(int x, int pos){for(int i = 1; i * i <= x; i++)if(x % i == 0) lst[i] = lst[x / i] = pos;
}int main(){freopen("drink.in","r",stdin);freopen("drink.out","w",stdout);int n, now = 0;ll ans = 0;scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= n; i++){if(a[i] > k){now = max(now, lst[0]);now = max(lst[a[i]], now);}  ans = ans + 1LL*(i - now);if(a[i] - k >= k) divi(a[i] - k, i);else if(a[i] == k) lst[0] = i;//printf("%d %d
 ", now, i);
    }printf("%lld
", ans);
} 

 

第三题：利用ai<=5000 的性质，搞一个（ai^2), 题解附在代码中

#include
using namespace std;
#define ll long long
const int M = 5005;
int f[M][M], a[1000005];
ll d[2][M], fac[M], P[M], mod;int main(){freopen("kalanchoe.in","r",stdin);freopen("kalanchoe.out","w",stdout);int n, m;scanf("%d%d%lld", &n, &m, &mod);for(int i = 1; i <= n; i++)scanf("%d", a + i);f[1][1] = 1; for(int i = 2; i <= 5000; i++)for(int j = 1; j <= 5000; j++)f[i][j] = ((ll)f[i - 1][j - 1] + (ll)f[i - 1][j] * (j - 1) % mod ) % mod;//f[i][j] 表示有i个空位放j个颜色的方案数，可以选择放一个新的颜色或者原来的颜色 fac[0] = 1;     P[1] = m;for(int i = 1; i <= 5000; i++) fac[i] = fac[i - 1] * i % mod;for(int i = 2; i <= 5000; i++) P[i] = P[i - 1] * (m - i + 1) % mod;   // 排列 for(int i = 1; i <= a[1]; i++) d[1][i] = (ll)f[a[1]][i] * P[i] % mod; //d[i][j]表示第i行放j种颜色的方案数，f只确定了位置，放什么颜色排列 int u = 1;for(int i = 2; i <= n; i++){u ^= 1;ll sum = 0;for(int j = 1; j <= a[i - 1]; j++) sum = (sum + d[u^1][j]) % mod;for(int j = 1; j <= a[i]; j++) {d[u][j] = (ll)f[a[i]][j] * P[j] % mod * sum % mod; //该行放j个的总方案数要乘上上一行的总方案数； if(j <= a[i - 1]) d[u][j] = ((d[u][j] - (ll)f[a[i]][j] * d[u^1][j] % mod * fac[j] % mod) + mod) % mod;//如果放的颜色比上一行总颜色种类少，那么可能会和上行颜色集合重复，我们强制这j种颜色和上行j种颜色同，怎么放就乘上fac[j] 
        }}ll ans = 0;for(int i = 1; i <= a[n]; i++) ans = (ans + d[u][i]) % mod;printf("%lld
", ans);
}