A 求导
幂函数求导n-1次,就是n的阶乘
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; int main(){ ll ans=1; ll n;cin>>n; for(int i=1;i<=n;i++){ ans=ans*i%mod; } cout<<ans<<endl; return 0; }
B 猜数
如果n个数总和≥m,那么直接输出0。
如果<m,贪心即可,从0开始,每次加上(9-k) 直到总和≥m
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; int a[15]; int main(){ ll n,m,x;cin>>n>>m; ll sum=0; for(int i=1;i<=n;i++) { cin>>x; a[x]++; sum+=x; } if(sum>=m) cout<<0<<endl; else { ll c=m-sum; int ans=0; for(int i=0;i<=9;i++){ while(a[i]){ if(c<=0) break; c-=(9-i); ans++; a[i]--; } if(c<=0) break; } cout<<ans<<endl; } return 0; }
C 答题卡
对于n阶的矩阵,考虑从n-1阶转移过来。 设f(n)为n阶矩阵满足的方案数
如果选择了(1,1)位置,那么就去掉了一行一列,那么就是f(n-1)的方案数。4
如果选择的第一行的其他位置,那么就去掉了两行两列,方案数就是f(n-2)。
因为除了第一个位置,还有n-1个位置,所以就是(n-1) * f(n-2)
递推式就是
比赛时候没想怎么推的,直接全排列打表找规律了。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll f[1 << 17]; void db() { int a[25] = {0}; for (int n = 1; n <= 10; n++) { for (int i = 1; i <= n; i++) a[i] = i; int ans = 0; do { int mp[15][15] = {0}; for (int i = 1; i <= n; i++) mp[i][a[i]] = 1; int flag = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (mp[i][j] != mp[j][i]) flag = 1; } } if (!flag) ans++; } while (next_permutation(a + 1, a + 1 + n)); cout << n << " " << ans << endl; } } int main() { //db(); ll n; cin >> n; f[1] = 1, f[2] = 2; for (int i = 3; i <= n; i++) f[i] = (f[i - 1] + (i - 1) * f[i - 2]) % mod; cout << f[n] << endl; return 0; }
D 待补