T2 B. 最小的公倍数小题
((10^L / 210) + 1) * 210 就是最小值
#include <bits/stdc++.h> using namespace std;int n; int main(){// for(int i = 2; i <= 18; i++){ // long long x = pow(10, i); // cout<<((x/210)+1)*210<<endl; // }cin>>n;if(n <= 2) {cout<<-1<<endl; return 0; }if(n == 3) {cout<<210<<endl; return 0;}cout<<1;for(int i = 1; i <= n-4; i++)cout<<"0";if(n%6 == 4) cout<<"050"<<endl;if(n%6 == 5) cout<<"080"<<endl;if(n%6 == 0) cout<<"170"<<endl;if(n%6 == 1) cout<<"020"<<endl;if(n%6 == 2) cout<<"200"<<endl;if(n%6 == 3) cout<<"110"<<endl;return 0; }
T4
/* n^3非常简单 dp[i][k] += dp[j][k-1] ( s[i] % k == s[j] % k && j < i ) 优化：可以设sum[s[i]%k][k-1] 是所有j小于i的dp[j][k-1]之和因此 sum[s[i]%k][k-1] += dp[j][k-1] */ #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 3e3+10,mod = 1e9+7; int n; ll a[N],sum[N][N],dp[N][N],s[N];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[i] = s[i-1] + a[i];}sum[0][0] = 1;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){dp[i][k] = sum[s[i]%k][k-1]; //所有小于k的j， dp[j][k-1]的前缀和 sum[s[i]%k](sum[s[i]%k][k-1] += dp[i][k-1]) %= mod;//保证转移给dp[i]里的是小于k的dp[j]，很妙 ,具体看下述解释# }}ll ans = 0;for(int i=1;i<=n;i++) ans = (ans + dp[n][i]%mod)%mod;cout<<ans<<endl;} /* # if(j < k) dp[i][k] = sum[s[i]%k][k-1]; //j<k这个隐形条件没法写 (sum[s[i]%k][k] += dp[i][k]) %= mod; //如果这样写的话，上面就得写条件，但显然这个条件没法写，因为我们并没有枚举j //sum[s[i]%k][k-1]表示前一列所有的dp[s[i]%k][k-1]的前缀和。没有办法控制行小于i */